Substrate-induced conformational change in a trimeric ornithine transcarbamoylase

The crystal structure of Escherichia coli ornithine transcarbamoylase (OTCase, EC 2.1.3.3) complexed with the bisubstrate analog N-(phosphonacetyl)-L-ornithine (PALO) has been determined at 2.8-A resolution. This research on the structure of a transcarbamoylase catalytic trimer with a substrate analog bound provides new insights into the linkages between substrate binding, protein-protein interactions, and conformational change. The structure was solved by molecular replacement with the Pseudomonas aeruginosa catabolic OTCase catalytic trimer (Villeret, V., Tricot, C., Stalon, V. & Dideberg, O. (1995) Proc. Natl. Acad. Sci. USA 92, 10762-10766; Protein Data Bank reference pdb 1otc) as the model and refined to a crystallographic R value of 21.3%. Each polypeptide chain folds into two domains, a carbamoyl phosphate binding domain and an L-ornithine binding domain. The bound inhibitor interacts with the side chains and/or backbone atoms of Lys-53, Ser-55, Thr-56, Arg-57, Thr-58, Arg-106, His-133, Asn-167, Asp-231, Met-236, Leu-274, Arg-319 as well as Gln-82 and Lys-86 from an adjacent chain. Comparison with the unligated P. aeruginosa catabolic OTCase structure indicates that binding of the substrate analog results in closure of the two domains of each chain. As in E. coli aspartate transcarbamoylase, the 240s loop undergoes the largest conformational change upon substrate binding. The clinical implications for human OTCase deficiency are discussed.     

Expressing the equivalence of non‐isothermal and isothermal heat sterilization processes

Currently, the sterility of heat‐processed food and pharmaceuticals is assessed in terms of an F₀ value, based on the equivalence of the heat treatment to an isothermal process at a reference temperature. This F₀ value, however, has a meaning if, and only if, the inactivation kinetics of the targeted spores (or cells) follow a first‐order relationship and the temperature dependence of the D value, the reciprocal of the rate constant, is log‐linear. There is growing evidence that these conditions are not satisfied by many spores, including those of Clostridium botulinum and vegetative cells. Consequently, a replacement for the F₀ value is proposed in the form of a momentary equivalent time at the reference temperature based on the actual survival pattern of the spores, which need not be log‐linear. This equivalent time can be calculated together with the theoretical survival ratio in real time, thus enabling an operator to monitor the lethality of ongoing industrial heat processes. The concept is demonstrated with published survival data of C. botulinum, for which the Weibullian and log‐logistic models served as primary and secondary models, respectively. The safety factor according to the proposed method is in the number of added minutes of processing, beyond the theoretical time needed to reduce the survival ratio of the targeted spores or cells to a level that would produce practical (or commercial) sterility. Copyright © 2006 Society of Chemical Industry     

On the use of the WLF model in polymers and foods.

The validity of the WLF model with fixed "universal" coefficients was tested against that of the model original form with variable coefficients using published coefficients of polymers and amorphous sugars crystallization and viscosity data. The disagreement between the two versions of the model is particularly large at temperature ranges starting about 20 to 30 degrees K above the glass transition or reference temperature, excluding the former from being a model of general applicability. Because the WLF model mathematical structure entails the existence of an almost linear region near the reference temperature, establishment of its validity as a kinetic model and meaningful determination of its constants requires data spread over an extended temperature range, especially when the experimental results have a scatter.     

Compact separator decompositions in dynamic trees and applications to labeling schemes

This paper presents an efficient scheme maintaining a separator decomposition representation in dynamic trees using asymptotically optimal labels. In order to maintain the short labels, the scheme uses relatively low message complexity. In particular, if the initial dynamic tree contains only the root, then the scheme incurs an O(log⁴ n) amortized message complexity per topology change, where n is the current number of vertices in the tree. As a separator decomposition is a fundamental decomposition of trees used extensively as a component in many static graph algorithms, our dynamic scheme for separator decomposition may be used for constructing dynamic versions to these algorithms. The paper then shows how to use our dynamic separator decomposition to construct efficient labeling schemes on dynamic trees, using the same message complexity as our dynamic separator scheme. Specifically, we construct efficient routing schemes on dynamic trees, for both the designer and the adversary port models, which maintain optimal labels, up to a multiplicative factor of O(log log n). In addition, it is shown how to use our dynamic separator decomposition scheme to construct dynamic labeling schemes supporting the ancestry and NCA relations using asymptotically optimal labels, as well as to extend a known result on dynamic distance labeling schemes. Supported in part at the Technion by an Aly Kaufman fellowship. Supported in part by a grant from the Israel Science Foundation.     

Honey bees find the shortest path: a collective flow-mediated approach

Artificial Life and Robotics - Honey bees (Apis mellifera L.) are social insects that makes frequent use of volatile pheromone signals to collectively navigate unpredictable and unknown...     

Labeling Schemes for Tree Representation

This paper deals with compact label-based representations for trees. Consider an n-node undirected connected graph G with a predefined numbering on the ports of each node. The all-ports tree labeling ℒ _all gives each node v of G a label containing the port numbers of all the tree edges incident to v. The upward tree labeling ℒ _up labels each node v by the number of the port leading from v to its parent in the tree. Our measure of interest is the worst case and total length of the labels used by the scheme, denoted M _up (T) and S _up (T) for ℒ _up and M _all (T) and S _all (T) for ℒ _all . The problem studied in this paper is the following: Given a graph G and a predefined port labeling for it, with the ports of each node v numbered by 0,…,deg (v)−1, select a rooted spanning tree for G minimizing (one of) these measures. We show that the problem is polynomial for M _up (T), S _up (T) and S _all (T) but NP-hard for M _all (T) (even for 3-regular planar graphs). We show that for every graph G and port labeling there exists a spanning tree T for which S _up (T)=O(nlog log n). We give a tight bound of O(n) in the cases of complete graphs with arbitrary labeling and arbitrary graphs with symmetric port labeling. We conclude by discussing some applications for our tree representation schemes. A preliminary version of this paper has appeared in the proceedings of the 7th International Workshop on Distributed Computing (IWDC), Kharagpur, India, December 27–30, 2005, as part of Cohen, R. et al.: Labeling schemes for tree representation. In: Proceedings of 7th International Workshop on Distributed Computing (IWDC), Lecture Notes of Computer Science, vol. 3741, pp. 13–24 (2005). R. Cohen supported by the Pacific Theaters Foundation. P. Fraigniaud and D. Ilcinkas supported by the project “PairAPair” of the ACI Masses de Données, the project “Fragile” of the ACI Sécurité et Informatique, and by the project “Grand Large” of INRIA. A. Korman supported in part by an Aly Kaufman fellowship. D. Peleg supported in part by a grant from the Israel Science Foundation.     

Approximation algorithm for hotlink assignment in the greedy model

Link-based information structures such as the web can be enhanced through the addition of hotlinks. Assume that each node in the information structure is associated with a weight representing the access frequency of the node by users. In order to access a particular node, the user must follow a path leading to it from the root. By adding new hotlinks to the tree, it may be possible to reduce the access cost of the system, namely, the expected number of steps needed to reach a leaf from the root, assuming the user can decide which hotlinks to follow in each step. The hotlink assignment   problem involves finding a set of hotlinks (with at most K=O(1)$K=O\left(1\right)$ hotlinks emanating from every node) maximizing the gain in the expected cost. The paper addresses this problem in two user models, namely, the traditional clairvoyant user model employed in [P. Bose, J. Czyzowicz, L. Gasieniec, E. Kranakis, D. Krizanc, A. Pelc, M.V. Martin, Strategies for hotlink assignments, in: Proc. 11th Symp. on Algorithms and Computation, 2000, pp. 23–34; E. Kranakis, D. Krizanc, S. Shende, Approximating hotlink assignments, in: Proc. 12th Symp. on Algorithms and Computation, 2001, pp. 756–767; P. Bose, D. Krizanc, S. Langerman, P. Morin, Asymmetrical communication protocols via hotlink assignments, in: Proc. 9th Colloq. on Structural Information and Communication Complexity, 2002, pp. 33–39; R. Matichin, D. Peleg, Approximation algorithm for hotlink assignments in web directories, in: Proc. Workshop on Algorithms and Data Structures, 2003, pp. 271–280] and the more realistic greedy user model recently introduced in [O. Gerstel, S. Kutten, R. Matichin, D. Peleg, Hotlink enhancement algorithms for web directories, in: Proc. 14th Symp. on Algorithms and Computation, 2003, pp. 68–77], and presents a polynomial time 2-approximation algorithm for the hotlink assignment problem on rooted directed trees.     

Labeling Schemes for Dynamic Tree Networks

Distance labeling schemes are composed of a marker algorithm for labeling the vertices of a graph with short labels, coupled with a decoder algorithm allowing one to compute the distance between any two vertices directly from their labels (without using any additional information). As applications for distance labeling schemes concern mainly large and dynamically changing networks, it is of interest to study distributed dynamic labeling schemes. The current paper considers the problem on dynamic trees, and proposes efficient distributed schemes for it. The paper first presents a labeling scheme for distances in the dynamic tree model, with amortized message complexity O(log² n) per operation, where n is the size of the tree at the time the operation takes place. The protocol maintains O(log² n) bit labels. This label size is known to be optimal even in the static scenario. A more general labeling scheme is then introduced for the dynamic tree model, based on extending an existing static tree labeling scheme to the dynamic setting. The approach fits a number of natural tree functions, such as distance, separation level, and flow. The main resulting scheme incurs an overhead of an O(log n) multiplicative factor in both the label size and amortized message complexity in the case of dynamically growing trees (with no vertex deletions). If an upper bound on n is known in advance, this method yields a different tradeoff, with an O(log² n/log log n) multiplicative overhead on the label size but only an O(log n/log log n) overhead on the amortized message complexity. In the fully dynamic model the scheme also incurs an increased additive overhead in amortized communication, of O(log² n) messages per operation.     

Deterministic Resource Discovery in Distributed Networks

The resource discovery problem was introduced by Harchol-Balter, Leighton, and Lewin. They developed a number of algorithms for the problem in the weakly connected directed graph model. This model is a directed logical graph that represents the vertices’ knowledge about the topology of the underlying communication network. The current paper proposes a deterministic algorithm for the problem in the same model, with improved time, message, and communication complexities. Each previous algorithm had a complexity that was higher at least in one of the measures. Specifically, previous deterministic solutions required either time linear in the diameter of the initial network, or communication complexity $O(n^3)$ (with message complexity $O(n^2)$), or message complexity $O(|E_0| \log n)$ (where $E_0$ is the arc set of the initial graph $G_0$). Compared with the main randomized algorithm of Harchol-Balter, Leighton, and Lewin, the time complexity is reduced from $O(\log^2n)$ to\pagebreak[4] $O(\log n )$, the message complexity from $O(n \log^2 n)$ to $O(n \log n )$, and the communication complexity from $O(n^2 \log^3 n)$ to $O(|E_0|\log ^2 n )$. \par Our work significantly extends the connectivity algorithm of Shiloach and Vishkin which was originally given for a parallel model of computation. Our result also confirms a conjecture of Harchol-Balter, Leighton, and Lewin, and addresses an open question due to Lipton.