Novel Zn(2+)-binding Sites in Human Transthyretin IMPLICATIONS FOR AMYLOIDOGENESIS AND RETINOL-BINDING PROTEIN RECOGNITION

Human transthyretin (TTR) is a homotetrameric protein involved in several amyloidoses. Zn(2+) enhances TTR aggregation in vitro, and is a component of ex vivo TTR amyloid fibrils. We report the first crystal structure of human TTR in complex with Zn(2+) at pH 4.6-7.5. All four structures reveal three tetra-coordinated Zn(2+)-binding sites (ZBS 1-3) per monomer, plus a fourth site (ZBS 4) involving amino acid residues from a symmetry-related tetramer that is not visible in solution by NMR.Zn(2+) binding perturbs loop E-alpha-helix-loop F, the region involved in holo-retinol-binding protein (holo-RBP) recognition, mainly at acidic pH; TTR affinity for holo-RBP decreases similar to 5-fold in the presence of Zn(2+). Interestingly, this same region is disrupted in the crystal structure of the amyloidogenic intermediate of TTR formed at acidic pH in the absence of Zn(2+). HNCO and HNCA experiments performed in solution at pH 7.5 revealed that upon Zn(2+) binding, although the alpha-helix persists, there are perturbations in the resonances of the residues that flank this region, suggesting an increase in structural flexibility. While stability of the monomer of TTR decreases in the presence of Zn(2+), which is consistent with the tertiary structural perturbation provoked by Zn(2+) binding, tetramer stability is only marginally affected by Zn(2+). These data highlight structural and functional roles of Zn(2+) in TTR-related amyloidoses, as well as in holo-RBP recognition and vitamin A homeostasis.

Recognition by the Thyroid Hormone Receptor of Canonical DNA Response Elements

To shed more light on the molecular requirements for recognition of thyroid response elements (TRES) by thyroid receptors (TRs), we compared the specific aspects of DNA TRE recognition by different TR constructs. Using fluorescence anisotropy, we performed a detailed and hierarchical study of TR-TRE binding. This wits done by comparing the binding affinities of three different TR constructs for four different TRE DNA elements, including palindromic sequences and direct repeats (F2, PAL, DR-1, and DR-4) as well as their interactions with nonspecific DNA sequences. The effect of MgCl(2) on suppressing of nonselective DNA binding to TR was also investigated. Furthermore, we determined the dissociation constants of the hTR beta DBD (DNA binding domain) and hTR beta DBD-LBD (DNA binding and ligand binding domains) for specific TRES. We found that a minimum DNA recognition peptide derived from DBD (H1TR) is sufficient for recognition and interaction with TREs, whereas scrambled DNA sequences were unrecognized. Additionally, we determined that the TR DBD binds to F2, PAL, and DR-4 with high affinity and similar K(d) values. The TR DBD-LBD recognizes all the tested TRES but binds preferentially to F2, with even higher affinity. Finally, our results demonstrate the important role played by LBDs in modulating TR-DNA binding.

Molecular Basis of the Thermostability and Thermophilicity of Laminarinases: X-ray Structure of the Hyperthermostable Laminarinase from Rhodothermus marinus and Molecular Dynamics Simulations

Glycosyl hydrolases are enzymes capable of breaking the glycosidic linkage of polysaccharides and have considerable industrial and biotechnological applications. Driven by the later applications, it is frequently desirable that glycosyl hydrolases display stability and activity under extreme environment conditions, such as high temperatures and extreme pHs. Here, we present X-ray structure of the hyperthermophilic laminarinase from Rhodothermus marinus (RmLamR) determined at 1.95 angstrom resolution and molecular dynamics simulation studies aimed to comprehend the molecular basis, for the thermal stability of this class of enzymes. As most thermostable proteins, RmLamR contains a relatively large number of salt bridges, which are not randomly distributed on the structure. On the contrary, they form clusters interconnecting beta-sheets of the catalytic domain. Not all salt bridges, however, are beneficial for the protein thermostability: the existence of charge-charge interactions permeating the hydrophobic core of the enzymes actually contributes to destabilize the structure by facilitating water penetration into hydrophobic cavities, as can be seen in the case of mesophilic enzymes. Furthermore, we demonstrate that the mobility of the side-chains is perturbed differently in each class of enzymes. The side-chains of loop residues surrounding the catalytic cleft in the mesophilic laminarinase gain mobility and obstruct the active site at high temperature. By contrast, thermophilic laminarinases preserve their active site flexibility, and the active-site cleft remains accessible for recognition of polysaccharide substrates even at high temperatures. The present results provide structural insights into the role played by salt-bridges and active site flexibility on protein thermal stability and may be relevant for other classes of proteins, particularly glycosyl hydrolases.

U-curve: A branch-and-bound optimization algorithm for U-shaped cost functions on Boolean lattices applied to the feature selection problem

This paper presents the formulation of a combinatorial optimization problem with the following characteristics: (i) the search space is the power set of a finite set structured as a Boolean lattice; (ii) the cost function forms a U-shaped curve when applied to any lattice chain. This formulation applies for feature selection in the context of pattern recognition. The known approaches for this problem are branch-and-bound algorithms and heuristics that explore partially the search space. Branch-and-bound algorithms are equivalent to the full search, while heuristics are not. This paper presents a branch-and-bound algorithm that differs from the others known by exploring the lattice structure and the U-shaped chain curves of the search space. The main contribution of this paper is the architecture of this algorithm that is based on the representation and exploration of the search space by new lattice properties proven here. Several experiments, with well known public data, indicate the superiority of the proposed method to the sequential floating forward selection (SFFS), which is a popular heuristic that gives good results in very short computational time. In all experiments, the proposed method got better or equal results in similar or even smaller computational time. (C) 2009 Elsevier Ltd. All rights reserved.

Approximation algorithms and hardness results for the clique packing problem

For a fixed family F of graphs, an F-packing in a graph G is a set of pairwise vertex-disjoint subgraphs of G, each isomorphic to an element of F. Finding an F-packing that maximizes the number of covered edges is a natural generalization of the maximum matching problem, which is just F = {K(2)}. In this paper we provide new approximation algorithms and hardness results for the K(r)-packing problem where K(r) = {K(2), K(3,) . . . , K(r)}. We show that already for r = 3 the K(r)-packing problem is APX-complete, and, in fact, we show that it remains so even for graphs with maximum degree 4. On the positive side, we give an approximation algorithm with approximation ratio at most 2 for every fixed r. For r = 3, 4, 5 we obtain better approximations. For r = 3 we obtain a simple 3/2-approximation, achieving a known ratio that follows from a more involved algorithm of Halldorsson. For r = 4, we obtain a (3/2 + epsilon)-approximation, and for r = 5 we obtain a (25/14 + epsilon)-approximation. (C) 2008 Elsevier B.V. All rights reserved.

Automatic contour extraction from 2D neuron images

This work describes a novel methodology for automatic contour extraction from 2D images of 3D neurons (e.g. camera lucida images and other types of 2D microscopy). Most contour-based shape analysis methods cannot be used to characterize such cells because of overlaps between neuronal processes. The proposed framework is specifically aimed at the problem of contour following even in presence of multiple overlaps. First, the input image is preprocessed in order to obtain an 8-connected skeleton with one-pixel-wide branches, as well as a set of critical regions (i.e., bifurcations and crossings). Next, for each subtree, the tracking stage iteratively labels all valid pixel of branches, tip to a critical region, where it determines the suitable direction to proceed. Finally, the labeled skeleton segments are followed in order to yield the parametric contour of the neuronal shape under analysis. The reported system was successfully tested with respect to several images and the results from a set of three neuron images are presented here, each pertaining to a different class, i.e. alpha, delta and epsilon ganglion cells, containing a total of 34 crossings. The algorithms successfully got across all these overlaps. The method has also been found to exhibit robustness even for images with close parallel segments. The proposed method is robust and may be implemented in an efficient manner. The introduction of this approach should pave the way for more systematic application of contour-based shape analysis methods in neuronal morphology. (C) 2008 Elsevier B.V. All rights reserved.

Algorithms for Maximum Independent Set in Convex Bipartite Graphs

A bipartite graph G = (V, W, E) is convex if there exists an ordering of the vertices of W such that, for each v. V, the neighbors of v are consecutive in W. We describe both a sequential and a BSP/CGM algorithm to find a maximum independent set in a convex bipartite graph. The sequential algorithm improves over the running time of the previously known algorithm and the BSP/CGM algorithm is a parallel version of the sequential one. The complexity of the algorithms does not depend on |W|.

Algorithms for two-dimensional cutting stock and strip packing problems using dynamic programming and column generation

We investigate several two-dimensional guillotine cutting stock problems and their variants in which orthogonal rotations are allowed. We first present two dynamic programming based algorithms for the Rectangular Knapsack (RK) problem and its variants in which the patterns must be staged. The first algorithm solves the recurrence formula proposed by Beasley; the second algorithm - for staged patterns - also uses a recurrence formula. We show that if the items are not so small compared to the dimensions of the bin, then these algorithms require polynomial time. Using these algorithms we solved all instances of the RK problem found at the OR-LIBRARY, including one for which no optimal solution was known. We also consider the Two-dimensional Cutting Stock problem. We present a column generation based algorithm for this problem that uses the first algorithm above mentioned to generate the columns. We propose two strategies to tackle the residual instances. We also investigate a variant of this problem where the bins have different sizes. At last, we study the Two-dimensional Strip Packing problem. We also present a column generation based algorithm for this problem that uses the second algorithm above mentioned where staged patterns are imposed. In this case we solve instances for two-, three- and four-staged patterns. We report on some computational experiments with the various algorithms we propose in this paper. The results indicate that these algorithms seem to be suitable for solving real-world instances. We give a detailed description (a pseudo-code) of all the algorithms presented here, so that the reader may easily implement these algorithms. (c) 2007 Elsevier B.V. All rights reserved.

Dynamic Changes in the Mental Rotation Network Revealed by Pattern Recognition Analysis of fMRI Data

We investigated the temporal dynamics and changes in connectivity in the mental rotation network through the application of spatio-temporal support vector machines (SVMs). The spatio-temporal SVM [Mourao-Miranda, J., Friston, K. J., et al. (2007). Dynamic discrimination analysis: A spatial-temporal SVM. Neuroimage, 36, 88-99] is a pattern recognition approach that is suitable for investigating dynamic changes in the brain network during a complex mental task. It does not require a model describing each component of the task and the precise shape of the BOLD impulse response. By defining a time window including a cognitive event, one can use spatio-temporal fMRI observations from two cognitive states to train the SVM. During the training, the SVM finds the discriminating pattern between the two states and produces a discriminating weight vector encompassing both voxels and time (i.e., spatio-temporal maps). We showed that by applying spatio-temporal SVM to an event-related mental rotation experiment, it is possible to discriminate between different degrees of angular disparity (0 degrees vs. 20 degrees, 0 degrees vs. 60 degrees, and 0 degrees vs. 100 degrees), and the discrimination accuracy is correlated with the difference in angular disparity between the conditions. For the comparison with highest accuracy (08 vs. 1008), we evaluated how the most discriminating areas (visual regions, parietal regions, supplementary, and premotor areas) change their behavior over time. The frontal premotor regions became highly discriminating earlier than the superior parietal cortex. There seems to be a parcellation of the parietal regions with an earlier discrimination of the inferior parietal lobe in the mental rotation in relation to the superior parietal. The SVM also identified a network of regions that had a decrease in BOLD responses during the 100 degrees condition in relation to the 0 degrees condition (posterior cingulate, frontal, and superior temporal gyrus). This network was also highly discriminating between the two conditions. In addition, we investigated changes in functional connectivity between the most discriminating areas identified by the spatio-temporal SVM. We observed an increase in functional connectivity between almost all areas activated during the 100 degrees condition (bilateral inferior and superior parietal lobe, bilateral premotor area, and SMA) but not between the areas that showed a decrease in BOLD response during the 100 degrees condition.

Fabrication of disposable voltammetric electronic tongues by using Prussian Blue films electrodeposited onto CD-R gold surfaces and recognition of milk adulteration

A new approach to fabricate a disposable electronic tongue is reported. The fabrication of the disposable sensor aimed the integration of all electrodes necessary for measurement in the same device. The disposable device was constructed with gold CD-R and copper sheets substrates and the sensing elements were gold, copper and a gold surface modified with a layer of Prussian Blue. The relative standard deviation for signals obtained from 20 different disposable gold and 10 different disposable copper electrodes was below 3.5%. The performance, electrode materials and the capability of the device to differentiate samples were evaluated for taste substances model, milk with different pasteurization processes (homogenized/pasteurized, ultra high temperature (UHT) pasteurized and UHT pasteurized with low fat content) and adulterated with hydrogen peroxide. In all analysed cases, a good separation between different samples was noticed in the score plots obtained from the principal component analysis (PCA). Crown Copyright (C) 2008 Published by Elsevier B.V. All rights reserved.