Physics-based simulation is needed to understand the function of biological structures and can be applied across a wide range of scales, from molecules to organisms. Simbios (the National Center for Physics-Based Simulation of Biological Structures, http://www.simbios.stanford.edu/) is one of seven NIH-supported National Centers for Biomedical Computation. This article provides an overview of the mission and achievements of Simbios, and describes its place within systems biology. Understanding the interactions between various parts of a biological system and integrating this information to understand how biological systems function is the goal of systems biology. Many important biological systems comprise complex structural systems whose components interact through the exchange of physical forces, and whose movement and function is dictated by those forces. In particular, systems that are made of multiple identifiable components that move relative to one another in a constrained manner are multibody systems. Simbios' focus is creating methods for their simulation. Simbios is also investigating the biomechanical forces that govern fluid flow through deformable vessels, a central problem in cardiovascular dynamics. In this application, the system is governed by the interplay of classical forces, but the motion is distributed smoothly through the materials and fluids, requiring the use of continuum methods. In addition to the research aims, Simbios is working to disseminate information, software and other resources relevant to biological systems in motion.

A special case of the dynamic finger conjecture is proved; this special case introduces a number of useful techniques.

The problem of comparing two sequences A and B to determine their longest common subsequence (LCS) or the edit distance between them has been much studied. In this paper we consider the following incremental version of these problems: given an appropriate encoding of a comparison between A and B, can one incrementally compute the answer for A and bB, and the answer for A and Bb with equal efficiency, where b is an additional symbol? Our main result is a theorem exposing a surprising relationship between the dynamic programming solutions for two such "adjacent" problems. Given a threshold k on the number of differences to be permitted in an alignment, the theorem leads directly to an O(k) algorithm for incrementally computing a new solution from an old one, as contrasts the O(k 2 ) time required to compute a solution from scratch. We further show, with a series of applications, that this algorithm is indeed more powerful than its nonincremental counterpart. We show this by solving the applications with greater asymptotic efficiency than heretofore possible. For example, we obtain O(nk) algorithms for the longest prefix approximate match problem, the approximate overlap problem, and cyclic string comparison.

Weighted paths in directed grid graphs of dimension (m X n) can be used to model the string edit problem, which consists of obtaining optimal (weighted) alignments between substrings of A, |A|=m, and substrings of B, |B|=n. We build a data structure (in O(mn log m) time) that supports O(log m) time queries about the weight of any of the O(m 2 n) best paths from the vertices in column 0 of the graph to all other vertices. Using these techniques we present a simple O(n 2 log n) time and $\Theta(n^2)$ space algorithm to find all (the locally optimal) approximate tandem (or nontandem) repeats xy within a string of size n. This improves (by a factor of log n) upon several previous algorithms for this problem and is the first algorithm to find all locally optimal repeats. For edit graphs with weights in {0, -1, 1}, a slight modification of our techniques yields an O(n 2 ) algorithm for the cyclic string comparison problem, as compared to O(n 2 log n) for the case of general weights.

We consider the problem of scheduling a parallel loop with independent iterations on a network of heterogeneous workstations, and demonstrate the effectiveness of a variant of factoring, a scheduling policy originating in the context of shared address-space homogeneous multiprocessors. In the new scheme, weighted factoring, processors are dynamically assigned decreasing size chunks of iterations in proportion to their processing speeds. Through experiments on a network of SUN Sparc workstations we show that weighted factoring significantly outperforms variants of a work-stealing load-balancing algorithm and on certain applications dramatically outperforms factoring as well. We then study weighted work assignment analytically, giving upper and lower bounds on its performance under the assumption that the processor iteration execution times can be modeled as weighted random variables. Department of Computer Science, Polytechnic University, Brooklyn, NY, 11201. Research supported by AR...

Chernoff–Hoeffding (CH) bounds are fundamental tools used in bounding the tail probabilities of the sums of bounded and independent random variables (r.v.’s). We present a simple technique that gives slightly better bounds than these and that more importantly requires only limited independence among the random variables, thereby importing a variety of standard results to the case of limited independence for free. Additional methods are also presented, and the aggregate results are sharp and provide a better understanding of the proof techniques behind these bounds. These results also yield improved bounds for various tail probability distributions and enable improved approximation algorithms for jobshop scheduling. The limited independence result implies that a reduced amount and weaker sources of randomness are sufficient for randomized algorithms whose analyses use the CH bounds, e.g., the analysis of randomized algorithms for random sampling and oblivious packet routing.

A general framework for solving multiple-line history queries is presented. The authors address two important historical queries in this environment: the vertical query and the horizontal query. The vertical query enables a design team to find what its design was at a past instant on its own path of evolution, while the horizontal query provides a design team with the designs of relevant teams at concurrent times in the past.>

Nonoblivious hashing, where information gathered from unsuccessful probes is used to modify subsequent probe strategy, is introduced and used to obtain the following results for static lookup on full tables: (1) An O (1)-time worst-case scheme that uses only logarithmic additional memory, (and no memory when the domain size is linear in the table size), which improves upon previously linear space requirements. (2) An almost sure O (1)-time probabilistic worst-case scheme, which uses no additional memory and which improves upon previously logarithmic time requirements. (3) Enhancements to hashing: (1) and (2) are solved for multikey recors, where search can be performed under any key in time O (1); these schemes also permit properties, such as nearest neighbor and rank, to be determined in logarithmic time.

This paper gives the first optimal bounds for classical closed hashing schemes in the case of limited randomness.We thereby establish the first proof of optimality for hashing arbitrarily selected data, by virtually any classical closed scheme, with hash functions that are programmable and initialized by a small number of random bits.Let D = (xl, x2,..., x~) be a sequence of an distinct search keys, for a < 1, belonging to the universe U = {0, 1,...,m}.The objective is to hash D into a search table without the use of pointers and without relocating placed items.We show that for any fixed load a < 1, universal classes of c log n-wise independent hash functions yield the same expected performance as fully random hash functions for uniform hashing, linear probing, and double hashing.That is, the expected number of probes to insert the an-th item is asymptotically the same for clog n-wise independent functions as for idealized fully random hash functions.It follows that O(loglog m + log s n) random bits suffice for these hash schemes.In addition, this relationship holds for the expected r-th moment of the probe count, for any fixed r, with an additive term of only O( n )due to the limited randomness.Our performance bound for double hashing readily applies to any robust generalization that exhibits approximate pairwise independence for the first O(logn) probes of any item.This result is new even in the case of full randomness.When combined with the highly independent fast hash functions of [S-89], these results give the first randomized algorithms featuring~ for a word model of computation, constant time per probe and optimal probe performance (for double hashing and uniform hashing).These results are derived from a novel formulation that overestimates the expected probe count by underestimating the presence of local items already inserted into the hash table, and from a sharp analysis of the underlying stochastic structures formed by colliding items.

The problem of constructing a dense static hash-based lookup table T for a set of n elements belonging to a universe $U = \{ 0, 1, 2,\cdots , m -1 \}$ is considered. Nearly tight bounds on the spatial complexity of oblivious $O(1)$-probe hash functions, which are defined to depend solely on their search key argument, are provided. This establishes a significant gap between oblivious and nonoblivious search. In particular, the results include the following: • A lower bound showing that oblivious k-probe hash functions require a program size of $\Omega(({n / k}^{2})e^{-k}+\log \log m)$ bits, on average. • A probabilistic construction of a family of oblivious k-probe hash functions that can be specified in $O(n e^{-k} +\log \log m)$ bits, which nearly matches the above lower bound. • A variation of an explicit $O(1)$ time 1-probe (perfect) hash function family that can be specified in $O(n+\log \log m)$ bits, which is tight to within a constant factor of the lower bound.

We consider two hashing models for storing a set S ⊂ {0, 1, 2, …, m - 1} in a table T of size n.

Non-oblivious hashing, where the information gathered by performing “unsuccessful” probes determines the probe strategy, is introduced and used to obtain the following results for static lookup on full tables:

We describe an implicit data structure for n multikey records that supports searching for a record, under any key, in the asymptotically optimal search time Ο(log n). This improves on [Mun87] in which Munro describes an implicit data structure for the problem of storing n k-key records so that search on any key can be performed in Ο(logk n(log log n)k-1) comparisons. The theoretical tools we develop also yield practical schemes that either halve the number of memory references over obvious solutions to the non-implicit version of the problem, or alternatively reduce the number of pointers involved significantly.