We consider the following multi-level opinion spreading model on networks. Initially, each node gets a weight, from the set {0,. . .,k – 1}, which measures the individual conviction of a new idea or product. Then, by proceeding in rounds, each node updates its weight according to those of its neighbours. We study k-dynamos that are initial assignments of weights leading each node to get the value k – 1 – e.g. unanimous maximum level of acceptance – within a given number of rounds; the goal is to minimize the sum of the initial weights of the nodes. We determine lower bounds on the sum of the initial weights under the irreversible simple majority rules, where a node increases its weight if and only if the majority of its neighbours have a weight that is higher than its own. We study the relations among 2-dynamos and k-dynamos, with and without a bound on the number of rounds needed to reach the desired all-(k – 1) configuration. Moreover, we provide constructive tight upper bounds for some classes of regular topologies: rings, tori and cliques.

BACKGROUND: Protein identification is one of the most challenging problems in proteomics. Tandem mass spectrometry provides an important tool to handle the protein identification problem. RESULTS: We developed a work-efficient parallel algorithm for the peptide sequence tag problem. The algorithm runs on the concurrent-read, exclusive-write PRAM in O(n) time using log n processors, where n is the number of mass peaks in the spectrum. The algorithm is able to find all the sequence tags having score greater than a parameter or all the sequence tags of maximum length. Our tests on 1507 spectra in the Open Proteomics Database shown that our algorithm is efficient and effective since achieves comparable results to other methods. CONCLUSIONS: The proposed algorithm can be used to speed up the database searching or to identify post-translational modifications, comparing the homology of the sequence tags found with the sequences in the biological database.

The approximate string matching problem (ASMP) consists of finding all the occurrences of a string of characters X of length m in another string Y of length n, m ≪ n, where some errors are allowed in these occurrences. A classical sequential algorithm based on dynamic programming solves the problem in time of O(mn). A parallelisation scheme for this algorithm is proposed, which applies to a very general set of errors, and allows to solve ASMP in time T with N processors, with NT of O(mn), thereby achieving optimal speedup. The scheme is suitable for VLSI implementation on a bounded degree network.

We present a parallel algorithm to solve the visibility problem among n vertical segments in a plane, which can be implemented on a VLSI chip arranged as a mesh of trees. Our algorithm determines all the pairs of segments that "see" each other in time O(log n); while the fastest sequential algorithm requires O(n log n). A lower bound to the area-time complexity of this problem of O(n2 log2 n) is also derived.

The problem of sorting n elements using VLSI chips that can sort only q(q < n) elements at a time is considered. The proposed VLSI chip consists of a mesh of trees. Two classical algorithms, i.e., merge sort and bitonic sort, are modified to efficiently solve the external sorting problem using this chip.

A VLSI chip for performing relational data base operations is proposed. The chip is a tree of processors (TOP), where each chip has elementary storage and processing capabilities. A relation will be stored in the lowest levels of a TOP. More precisely, every m-tuple will occupy a subtree whose root is s= [log2(m+1)] =1 levels above the leaves. Denoting by h the height of the tree, the upper h-s levels will be used for routing and bookkeeping purposes. A number of basic operations such as allocate and deallocate subtrees, insert and compare m-tuples etc., are defined for the TOP's. Relational operations are effectively performed as simple combinations of basic operations. The architecture of a data base machine based on TOP's is also sketched. Such a machine is feasible with the current VLSI technology and could become attractive in few years if density and performance of VLSI keep improving at the current rate.