Insights based on detailed data on consumer behavior, product performance and marketplace behavior are driving innovation and competition in the internet space. We introduce Everest, a SQL-compliant data warehousing engine, based on a column architecture that we have built and deployed at Yahoo!. In contrast to commercially available engines, this massively parallel engine, based on commodity hardware, offers scale, flexibility, specialized analytic operations, and lower administrative & hardware costs. In this paper, we describe the business motivation and the software and deployment architecture of Everest. The engine is in production at Yahoo! since 2007 and currently manages over six petabytes of data.

MOTIVATION: Until ab initio structure prediction methods are perfected, the estimation of structure for protein molecules will depend on combining multiple sources of experimental and theoretical data. Secondary structure predictions are a particularly useful source of structural information, but are currently only approximately 70% correct, on average. Structure computation algorithms which incorporate secondary structure information must therefore have methods for dealing with predictions that are imperfect. EXPERIMENTS PERFORMED: We have modified our algorithm for probabilistic least squares structural computations to accept 'disjunctive' constraints, in which a constraint is provided as a set of possible values, each weighted with a probability. Thus, when a helix is predicted, the distances associated with a helix are given most of the weight, but some weights can be allocated to the other possibilities (strand and coil). We have tested a variety of strategies for this weighting scheme in conjunction with a baseline synthetic set of sparse distance data, and compared it with strategies which do not use disjunctive constraints. RESULTS: Naive interpretations in which predictions were taken as 100% correct led to poor-quality structures. Interpretations that allow disjunctive constraints are quite robust, and even relatively poor predictions (58% correct) can significantly increase the quality of computed structures (almost halving the RMS error from the known structure). CONCLUSIONS: Secondary structure predictions can be used to improve the quality of three-dimensional structural computations. In fact, when interpreted appropriately, imperfect predictions can provide almost as much improvement as perfect predictions in three-dimensional structure calculations.

The task of computing molecular structure from combinations of experimental and theoretical constraints is expensive because of the large number of estimated parameters (the 3D coordinates of each atom) and the rugged landscape of many objective functions. For large molecular ensembles with multiple protein and nucleic acid components, the problem of maintaining tractability in structural computations becomes critical. A well known strategy for solving difficult problems is divide and conquer. For molecular computations, there are two ways in which problems can be divided: (1) using the natural hierarchy within biological macromolecules (taking advantage of primary sequence, secondary structural subunits and tertiary structural motifs, when they are known), and (2) using the hierarchy that results from analyzing the distribution of structural constraints (providing information about which substructures are constrained to one another). In this paper, we show that these two hierarchies can be complementary and can provide information for efficient decomposition of structural computations. We demonstrate four methods for building such hierarchies---two automated heuristics that use both natural and empirical hierarchies, one knowledge-based process using both hierarchies, and one method based on the natural hierarchy alone---and apply them to a data set for the procaryotic 30S ribosomal subunit using our probabilistic least squares structure estimation algorithm. We show that the three methods that combine natural hierarchies with empirical hierarchies create decompositions which increase the empirical efficiency of computations by as much as 50-fold. There is only half this gain when using the natural decomposition alone. Although the knowledge-based method performs margi...

Determining the structure of biological macromolecules such as proteins and nucleic acids is an important element of molecular biology because of the intimate relation between form and function of these molecules. Individual sources of data about molecular structure are subject to varying degrees of uncertainty. Previously we have examined the parallelization of a probabilistic algorithm for combining multiple sources of uncertain data to estimate the three-dimensional structure of molecules and also predict a measure of the uncertainty in the estimated structure. In this paper we extend our work on two major fronts. First we present a hierarchiacal decomposition of the original algorithm which reduces the sequential computational complexity tremendously. The hierarchical decomposition in turn reveals a new axis of parallelism not present in the "flat" organization of the problems, as well as new parallelization problems. We demonstrate good speedups on two cache-coherent shared-memory multiprocessors, the Stanford DASH and the SGI Challenge, with distributed and centralized memory organization, respectively. Our results point to several areas of further study to make both the hierarchiacal and the parallel aspects more flexible for general problems: automatic structure decomposition, processor load balancing across the hierarchy, and data locality management in conjunction with load balancing. Finally we outline the directions we are investigating to incorporate these extensions.

The problem of computing a molecular structure from a set of distances arises in the interpretation of NMR data as well as other experimental methods that yield distance information. Techniques for computing structures must find conformations consistent with the distance data. There are often other constraints on the structure that must be satisfied as well. One of the most problematic constraints is the constraint on the total volume occupied by the atoms. In this paper, we use the first two moments (mean and variance) of an estimated distance distribution to constrain the volume of a computed structure. We show that a probabilistic algorithm for matching the first two moments of the estimated distance distribution significantly improves the quality of the solution, especially when the distance information alone is not sufficient to define the structure precisely. We also show that our method is not sensitive to small errors in the estimates of mean and variance of the distance distribution. Finally, we demonstrate the use of this constraint in computing a low-resolution structure of the 30S prokaryotic ribosomal subunit. Quantitative analysis of our results allows us to assess the information content contained in constraints on volume, and to show that in some cases addition of a volume constraint adds information roughly equivalent to doubling the number of input distances. Our results also demonstrate the flexibility of probabilistic representations of structural constraints, and the importance of including volume information to constrain structural computations-especially in the case of sparse data.

Molecular structure determination is an important task in biology because of the intimate relation between form and function of biological molecules. Individual sources of information about molecular structure are subject to uncertainty and are not sufficiently abundant to define the structure to high accuracy by themselves. The authors have examined a probabilistic algorithm, PROTEAN, which can incorporate multiple sources of uncertain data to estimate the three dimensional structure of molecules and also predict a measure of the uncertainty in the estimated structure. They have applied this algorithm successfully to several biological structure problems. Like most structure prediction methods, this algorithm is computationally expensive for realistic biological macromolecules. The authors experiment with speeding up the algorithm through the application of parallelism. They present a parallel version of the algorithm, and demonstrate good speedups on a 32-processor Stanford DASH, a cache coherent shared address space multiprocessor. The results were obtained by exploiting data locality only in the per-processor coherent caches, without attempt to distribute data intelligently in the physically distributed main memory of the machine. The authors also obtained very good speedups on a state of the art commercial multiprocessor, the Silicon Graphics Challenge. Finally, the authors propose an extension to the serial algorithm which enables it to handle a wider class of data, and discuss the potential for parallelization of the extended algorithm.>