Biomedical subjects

Chris Bailey-Kellogg

Publications and source records attributed to Chris Bailey-Kellogg.

11 recordsLinked to original sources

PubMed2006

Structure determination of symmetric homo-oligomers by a complete search of symmetry configuration space, using NMR restraints and van der Waals packing.

Structural studies of symmetric homo-oligomers provide mechanistic insights into their roles in essential biological processes, including cell signaling and cellular regulation. This paper presents a novel algorithm for homo-oligomeric structure determination, given the subunit structure, that is both complete, in that it evaluates all possible conformations, and data-driven, in that it evaluates conformations separately for consistency with experimental data and for quality of packing. Completeness ensures that the algorithm does not miss the native conformation, and being data-driven enables it to assess the structural precision possible from data alone. Our algorithm performs a branch-and-bound search in the symmetry configuration space, the space of symmetry axis parameters (positions and orientations) defining all possible C(n) homo-oligomeric complexes for a given subunit structure. It eliminates those symmetry axes inconsistent with intersubunit nuclear Overhauser effect (NOE) distance restraints and then identifies conformations representing any consistent, well-packed structure to within a user-defined similarity level. For the human phospholamban pentamer in dodecylphosphocholine micelles, using the structure of one subunit determined from a subset of the experimental NMR data, our algorithm identifies a diverse set of complex structures consistent with the nine intersubunit NOE restraints. The distribution of determined structures provides an objective characterization of structural uncertainty: backbone RMSD to the previously determined structure ranges from 1.07 to 8.85 A, and variance in backbone atomic coordinates is an average of 12.32 A(2). Incorporating vdW packing reduces structural diversity to a maximum backbone RMSD of 6.24 A and an average backbone variance of 6.80 A(2). By comparing data consistency and packing quality under different assumptions of oligomeric number, our algorithm identifies the pentamer as the most likely oligomeric state of phospholamban, demonstrating that it is possible to determine the oligomeric number directly from NMR data. Additional tests on a number of homo-oligomers, from dimer to heptamer, similarly demonstrate the power of our method to provide unbiased determination and evaluation of homo-oligomeric complex structures.

Algorithms↗

PubMed2006

Site-directed combinatorial construction of chimaeric genes: general method for optimizing assembly of gene fragments.

Site-directed construction of chimaeric genes by in vitro recombination "mixes-and-matches" precise building blocks from multiple parent proteins, generating libraries of hybrids to be tested for structure-function relationships and/or screened for favorable properties and novel enzymatic activities. A direct annealing and ligation method can construct chimaeric genes without requiring sequence identity between parents, except for the short (approximately 3 nt) sequences of the fragment overhangs used for specific ligation. Careful planning of the assembly process is necessary, though, in order to ensure effective construction of desired fragment assemblies and to avoid undesired assemblies (e.g., repetition of fragments, fragments out of order). We develop algorithms for specific planned ligation of short overhangs (SPLISO) that efficiently explore possible assembly plans, varying the fragment overhangs and the order of ligation steps in the assembly pathway. While there is a combinatorial explosion in the number of possible assembly plans as the number of breakpoints and parent genes increases, we employ a dynamic programming approach to find globally optimal ones in low-order polynomial time (in practice, taking only seconds for basic assembly plans). We demonstrate the effectiveness of our algorithms in planning the assembly of hybrid libraries, under a variety of experimental options and restrictions, including flexibility in the position and amino acid sequence of breakpoints. Our method promises to enable more effective application of site-directed recombination to protein investigation and engineering.

Algorithms↗

PubMed2006

Functional evolution within a protein superfamily.

The ability to predict and characterize distributions of reactivities over families and even superfamilies of proteins opens the door to an array of analyses regarding functional evolution. In this article, insights into functional evolution in the Kazal inhibitor superfamily are gained by analyzing and comparing predicted association free energy distributions against six serine proteinases, over a number of groups of inhibitors: all possible Kazal inhibitors, natural avian ovomucoid first and third domains, and sets of Kazal inhibitors with statistically weighted combinations of residues. The results indicate that, despite the great hypervariability of residues in the 10 proteinase-binding positions, avian ovomucoid third domains evolved to inhibit enzymes similar to the six enzymes selected, whereas the orthologous first domains are not inhibitors of these enzymes on purpose. Hypervariability arises because of similarity in energetic contribution from multiple residue types; conservation is in terms of functionality, with "good" residues, which make positive or less deleterious contributions to the binding, selected more frequently, and yielding overall the same distributional characteristics. Further analysis of the distributions indicates that while nature did optimize inhibitor strength, the objective may not have been the strongest possible inhibitor against one enzyme but rather an inhibitor that is relatively strong against a number of enzymes.

Amino Acid Sequence↗

PubMed2006

Inferential backbone assignment for sparse data.

This paper develops an approach to protein backbone NMR assignment that effectively assigns large proteins while using limited sets of triple-resonance experiments. Our approach handles proteins with large fractions of missing data and many ambiguous pairs of pseudoresidues, and provides a statistical assessment of confidence in global and position-specific assignments. The approach is tested on an extensive set of experimental and synthetic data of up to 723 residues, with match tolerances of up to 0.5 ppm for Calpha and Cbeta resonance types. The tests show that the approach is particularly helpful when data contain experimental noise and require large match tolerances. The keys to the approach are an empirical Bayesian probability model that rigorously accounts for uncertainty in the data at all stages in the analysis, and a hybrid stochastic tree-based search algorithm that effectively explores the large space of possible assignments.

Algorithms↗

PubMed2005

An efficient randomized algorithm for contact-based NMR backbone resonance assignment.

MOTIVATION: Backbone resonance assignment is a critical bottleneck in studies of protein structure, dynamics and interactions by nuclear magnetic resonance (NMR) spectroscopy. A minimalist approach to assignment, which we call 'contact-based', seeks to dramatically reduce experimental time and expense by replacing the standard suite of through-bond experiments with the through-space (nuclear Overhauser enhancement spectroscopy, NOESY) experiment. In the contact-based approach, spectral data are represented in a graph with vertices for putative residues (of unknown relation to the primary sequence) and edges for hypothesized NOESY interactions, such that observed spectral peaks could be explained if the residues were 'close enough'. Due to experimental ambiguity, several incorrect edges can be hypothesized for each spectral peak. An assignment is derived by identifying consistent patterns of edges (e.g. for alpha-helices and beta-sheets) within a graph and by mapping the vertices to the primary sequence. The key algorithmic challenge is to be able to uncover these patterns even when they are obscured by significant noise. RESULTS: This paper develops, analyzes and applies a novel algorithm for the identification of polytopes representing consistent patterns of edges in a corrupted NOESY graph. Our randomized algorithm aggregates simplices into polytopes and fixes inconsistencies with simple local modifications, called rotations, that maintain most of the structure already uncovered. In characterizing the effects of experimental noise, we employ an NMR-specific random graph model in proving that our algorithm gives optimal performance in expected polynomial time, even when the input graph is significantly corrupted. We confirm this analysis in simulation studies with graphs corrupted by up to 500% noise. Finally, we demonstrate the practical application of the algorithm on several experimental beta-sheet datasets. Our approach is able to eliminate a large majority of noise edges and to uncover large consistent sets of interactions. AVAILABILITY: Our algorithm has been implemented in the platform-independent Python code. The software can be freely obtained for academic use by request from the authors.

Algorithms↗

PubMed2005

Reconsidering complete search algorithms for protein backbone NMR assignment.

MOTIVATION: Nuclear magnetic resonance (NMR) spectroscopy is widely used to determine and analyze protein structures. An essential step in NMR studies is determining the backbone resonance assignment, which maps individual atoms to experimentally measured resonance frequencies. Performing assignment is challenging owing to the noise and ambiguity in NMR spectra. Although automated procedures have been investigated, by-and-large they are still struggling to gain acceptance because of inherent limits in scalability and/or unacceptable levels of assignment error. To have confidence in the results, an algorithm should be complete, i.e. able to identify all solutions consistent with the data, including all arbitrary configurations of extra and missing peaks. The ensuing combinatorial explosion in the space of possible assignments has led to the perception that complete search is hopelessly inefficient and cannot scale to realistic datasets. RESULTS: This paper presents a complete branch-contract-and-bound search algorithm for backbone resonance assignment. The algorithm controls the search space by hierarchically agglomerating partial assignments and employing statistically sound pruning criteria. It considers all solutions consistent with the data, and uniformly treats all combinations of extra and missing data. We demonstrate our approach on experimental data from five proteins ranging in size from 70 to 154 residues. The algorithm assigns >95% of the positions with >98% accuracy. We also present results on simulated data from 259 proteins from the RefDB database, ranging in size from 25 to 257 residues. The median computation time for these cases is 1 min, and the assignment accuracy is >99%. These results demonstrate that complete search not only has the advantage of guaranteeing fair treatment of all feasible solutions, but is efficient enough to be employed effectively inpractice. AVAILABILITY: The MBA(2) software package is made available under an open-source software license. The datasets featured in the Results section can also be obtained from the contact author.

Algorithms↗

PubMed2005

Analysis of sequence-reactivity space for protein-protein interactions.

Sequence-reactivity space is defined by the relationships between amino acid type choices at some residue positions in a protein and the reactivities of the resulting variants. We are studying Kazal superfamily serine proteinase inhibitors, under substitution of any combination of residue types at 10 binding-region positions. Reactivities are defined by the standard free energy of association for an inhibitor against an enzyme, and we are interested in both the strength (the free energy value) and specificity (relative free energy values for one inhibitor against different enzymes). Characterizing the structure of such a space poses several interesting questions: (1) How many sequences achieve particular strength and specificity characteristics? (2) What is the best such sequence? (3) What are some nearly-as-good alternatives? (4) What are their common residue type characteristics (e.g., conservation and correlation)? Although these problems are all highly combinatorial in nature, this article develops an efficient, integrated mechanism to address them under a data-driven model that predicts reactivity for given sequences. We employ sampling and a novel deterministic distribution propagation algorithm, in order to determine both the reactivity distribution and sequence composition statistics; integer programming and a novel branch-and-bound search algorithm, in order to optimize sequences and enumerate near-optimal sequences; and correlation-based sequence decomposition, in order to identify sequence motifs. We demonstrate the value of our mechanism in analyzing the Kazal superfamily sequence-reactivity space, providing insights into the underlying biochemistry and suggesting hypotheses for further experimental consideration. In general, our mechanism offers a valuable tool for investigating the available degrees of freedom in protein design within a combined computational-experimental framework.

Algorithms↗

PubMed2004

A subgroup algorithm to identify cross-rotation peaks consistent with non-crystallographic symmetry.

Molecular replacement (MR) often plays a prominent role in determining initial phase angles for structure determination by X-ray crystallography. In this paper, an efficient quaternion-based algorithm is presented for analyzing peaks from a cross-rotation function in order to identify model orientations consistent with proper non-crystallographic symmetry (NCS) and to generate proper NCS-consistent orientations missing from the list of cross-rotation peaks. The algorithm, CRANS, analyzes the rotation differences between each pair of cross-rotation peaks to identify finite subgroups. Sets of rotation differences satisfying the subgroup axioms correspond to orientations compatible with the correct proper NCS. The CRANS algorithm was first tested using cross-rotation peaks computed from structure-factor data for three test systems and was then used to assist in the de novo structure determination of dihydrofolate reductase-thymidylate synthase (DHFR-TS) from Cryptosporidium hominis. In every case, the CRANS algorithm runs in seconds to identify orientations consistent with the observed proper NCS and to generate missing orientations not present in the cross-rotation peak list. The CRANS algorithm has application in every molecular-replacement phasing effort with proper NCS.

Algorithms↗

PubMed2004

Model-based assignment and inference of protein backbone Nuclear Magnetic Resonances.

Nuclear Magnetic Resonance (NMR) spectroscopy is a key experimental technique used to study protein structure, dynamics, and interactions. NMR methods face the bottleneck of spectral analysis, in particular determining the resonance assignments, which help define the mapping between atoms in the protein and peaks in the spectra. A substantial amount of noise in spectral data, along with ambiguities in interpretation, make this analysis a daunting task, and there exists no generally accepted measure of uncertainty associated with the resulting solutions. This paper develops a model-based inference approach that addresses the problem of characterizing uncertainty in backbone resonance assignment. We argue that NMR spectra are subject to random variation, and ignoring this stochasticity can lead to false optimism and erroneous conclusions. We propose a Bayesian statistical model that accounts for various sources of uncertainty and provides an automatable framework for inference. While assignment has previously been viewed as a deterministic optimization problem, we demonstrate the importance of considering all solutions consistent with the data, and develop an algorithm to search this space within our statistical framework. Our approach is able to characterize the uncertainty associated with backbone resonance assignment in several ways: 1) it quantifies of uncertainty in the individually assigned resonances in terms of their posterior standard deviations; 2) it assesses the information content in the data with a posterior distribution of plausible assignments; and 3) it provides a measure of the overall plausibility of assignments. We demonstrate the value of our approach in a study of experimental data from two proteins, Human Ubiquitin and Cold-shock protein A from E. coli. In addition, we provide simulations showing the impact of experimental conditions on uncertainty in the assignments.

Journal Article↗

PubMed2004

Probabilistic cross-link analysis and experiment planning for high-throughput elucidation of protein structure.

Emerging high-throughput techniques for the characterization of protein and protein-complex structures yield noisy data with sparse information content, placing a significant burden on computation to properly interpret the experimental data. One such technique uses cross-linking (chemical or by cysteine oxidation) to confirm or select among proposed structural models (e.g., from fold recognition, ab initio prediction, or docking) by testing the consistency between cross-linking data and model geometry. This paper develops a probabilistic framework for analyzing the information content in cross-linking experiments, accounting for anticipated experimental error. This framework supports a mechanism for planning experiments to optimize the information gained. We evaluate potential experiment plans using explicit trade-offs among key properties of practical importance: discriminability, coverage, balance, ambiguity, and cost. We devise a greedy algorithm that considers those properties and, from a large number of combinatorial possibilities, rapidly selects sets of experiments expected to discriminate pairs of models efficiently. In an application to residue-specific chemical cross-linking, we demonstrate the ability of our approach to plan experiments effectively involving combinations of cross-linkers and introduced mutations. We also describe an experiment plan for the bacteriophage lambda Tfa chaperone protein in which we plan dicysteine mutants for discriminating threading models by disulfide formation. Preliminary results from a subset of the planned experiments are consistent and demonstrate the practicality of planning. Our methods provide the experimenter with a valuable tool (available from the authors) for understanding and optimizing cross-linking experiments.

Algorithms↗

PubMedDate not supplied

A random graph approach to NMR sequential assignment.

Nuclear magnetic resonance (NMR) spectroscopy allows scientists to study protein structure, dynamics and interactions in solution. A necessary first step for such applications is determining the resonance assignment, mapping spectral data to atoms and residues in the primary sequence. Automated resonance assignment algorithms rely on information regarding connectivity (e.g., through-bond atomic interactions) and amino acid type, typically using the former to determine strings of connected residues and the latter to map those strings to positions in the primary sequence. Significant ambiguity exists in both connectivity and amino acid type information. This paper focuses on the information content available in connectivity alone and develops a novel random-graph theoretic framework and algorithm for connectivity-driven NMR sequential assignment. Our random graph model captures the structure of chemical shift degeneracy, a key source of connectivity ambiguity. We then give a simple and natural randomized algorithm for finding optimal assignments as sets of connected fragments in NMR graphs. The algorithm naturally and efficiently reuses substrings while exploring connectivity choices; it overcomes local ambiguity by enforcing global consistency of all choices. By analyzing our algorithm under our random graph model, we show that it can provably tolerate relatively large ambiguity while still giving expected optimal performance in polynomial time. We present results from practical applications of the algorithm to experimental datasets from a variety of proteins and experimental set-ups. We demonstrate that our approach is able to overcome significant noise and local ambiguity in identifying significant fragments of sequential assignments.

Algorithms↗