1980658
Geometric Sieving: Automated Distributed Optimization of 3D Motifs for Protein Function Prediction
Determining the function of all proteins is a recurring theme in modern biology and medicine, but the sheer number of proteins makes experimental approaches impractical. For this reason, current efforts have considered in silico function prediction in order to guide and accelerate the function determination process. One approach to predicting protein function is to search functionally uncharacterized protein structures (targets), for substructures with geometric and chemical similarity (matches), to known active sites (motifs). Finding a match can imply that the target has an active site similar to the motif, suggesting functional homology. 
 
An effective function predictor requires effective motifs – motifs whose geometric and chemical characteristics are detected by comparison algorithms within functionally homologous targets (sensitive motifs), which also are not detected within functionally unrelated targets (specific motifs). Designing effective motifs is a difficult open problem. Current approaches select and combine structural, physical, and evolutionary properties to design motifs that mirror functional characteristics of active sites. 
 
We present a new approach, Geometric Sieving (GS), which refines candidate motifs into optimized motifs with maximal geometric and chemical dissimilarity from all known protein structures. The paper discusses both the usefulness and the efficiency of GS. We show that candidate motifs from six well-studied proteins, including α-Chymotrypsin, Dihydrofolate Reductase, and Lysozyme, can be optimized with GS to motifs that are among the most sensitive and specific motifs possible for the candidate motifs. For the same proteins, we also report results that relate evolutionarily important motifs with motifs that exhibit maximal geometric and chemical dissimilarity from all known protein structures. Our current observations show that GS is a powerful tool that can complement existing work on motif design and protein function prediction.
172784
Algorithms for Structural Comparison and Statistical Analysis of 3D Protein Motifs
The comparison of structural subsites in proteins is increasingly relevant to the prediction of their biological function. To address this problem, we present the Match Augmentation algorithm (MA). Given a structural motif of interest, such as a functional site, MA searches a target protein structure for a match: the set of atoms with the greatest geometric and chemical similarity. MA is extremely efficient because it exploits the fact that the amino acids in a structural motif are not equally important to function. Using motif residues ranked on functional significance via the Evolutionary Trace (ET), MA prioritizes its search by initially forming matches with functionally significant residues, then, guided by ET, it augments this partial match stepwise until the whole motif is found. With this hierarchical strategy, MA runs considerably faster than other methods, and almost always identifies matches in homologs known to have cognate functional sites. Second, in order to interpret matches, we further introduce a statistical method using nonparametric density estimation of the frequency distribution of structural matches. Our results show that the hierarchy of functional importance within structural motifs speeds up the search within targets, and points to a new method to score their statistical significance.
39846081
On-Line Algorithms for Cardinality Constrained Bin Packing Problems
The bin packing problem asks for a packing of a list of items from [0, 1] into the smallest possible number of bins having unit capacity. The k-item bin packing problem additionally imposes the constraint that at most k items are allowed in one bin. We present two efficient approximation algorithms for the on-line version of this problem. We show that, for increasing values of k, the asymptotic worst-case performance ratio of the first algorithm tends towards 2 and that the second algorithm has an asymptotic worst-case performance ratio of 2. Both heuristics considerably improve upon the best known result 2.7 of Krause, Shen and Schwetman. Moreover, we present algorithms for k = 2 and k = 3, where the result for k = 2 is best possible.
11232632
Interactive deformation of light fields
We present a software pipeline that enables an animator to deform light fields. The pipeline can be used to deform complex objects, such as furry toys, while maintaining photo-realistic quality. Our pipeline consists of three stages. First, we split the light field into sub-light fields. To facilitate splitting of complex objects, we employ a novel technique based on projected light patterns. Second, we deform each sub-light field. To do this, we provide the animator with controls similar to volumetric free-form deformation. Third, we recombine and render each sub-light field. Our rendering technique properly handles visibility changes due to occlusion among sub-light fields. To ensure consistent illumination of objects after they have been deformed, our light fields are captured with the light source fixed to the camera, rather than being fixed to the object. We demonstrate our deformation pipeline using synthetic and photographically acquired light fields. Potential applications include animation, interior design, and interactive gaming.
4000958
A Better Heuristic for Preemptive Parallel Machine Scheduling with Batch Setup Times
This paper addresses the problem of scheduling N jobs on M identical parallel machines with the objective of minimizing the makespan. Jobs are divided into B batches. A sequence-independent batch setup time on a machine is incurred whenever the machine starts its processing on or switches it from a job in one batch to a job in another batch. On the basis of a heuristic for this NP-hard problem proposed by Monma and Potts, a modified heuristic that requires the same implementing time $O(N + (M + B)\log (M + B))$ and is asymptotically optimal is presented. Furthermore, for a certain class of problems, which includes the case in which each batch contains a single job, it has the worst-case performance ratio $\tau _M = \max \{ {\frac{{3M}}{{2M + 1}},\frac{{3M - 4}}{{2M - 2}}} \}$.
4025640
Algorithms for on-line bin-packing problems with cardinality constraints
The bin-packing problem asks for a packing of a list of items of sizes from (0,1] into the smallest possible number of bins having unit capacity. The k-item bin-packing problem additionally imposes the constraint that at most k items are allowed in one bin. We present two efficient on-line algorithms for this problem. We show that, for increasing values of k, the bound on the asymptotic worst-case performance ratio of the first algorithm tends towards 2 and that the second algorithm has a ratio of 2. Both algorithms considerably improve upon the best known result of an algorithm, which has an asymptotic bound of 2.7 on its ratio. Moreover, we improve known bounds for all values of k by presenting on-line algorithms for k = 2 and 3 with bounds on their ratios close to optimal.
987186
Implementing Minimized Multivariate PKC on Low-Resource Embedded Systems
Multivariate (or $\mathcal{MQ}$) public-key cryptosystems (PKC) are alternatives to traditional PKCs based on large algebraic structures (e.g., RSA and ECC); they usually execute much faster than traditional PKCs on the same hardware. However, one major challenge in implementing multivariates in embedded systems is that the key size can be prohibitively large for applications with stringent resource constraints such as low-cost smart cards, sensor networks (e.g., Berkeley motes), and radio-frequency identification (RFID). In this paper, we investigate strategies for shortening the key of a multivariate PKC. We apply these strategies to the Tame Transformation Signatures (TTS) as an example and quantify the improvement in key size and running speed, both theoretically and via implementation. We also investigate ways to save die space and energy consumption in hardware, reporting on our ASIC implementation of TTS on a TSMC 0.25μm process. Even without any key shortening, the current consumption of TTS is only 21 μA for computing a signature, using 22,000 gate equivalents and 16,000 100-kHz cycles (160 ms). With circulant-matrix key shortening, the numbers go down to 17,000 gates and 4,400 cycles (44 ms). We therefore conclude: besides representing a future-proofing investment against the emerging quantum computers, multivariates can be immediately useful in niches.