Catálogo de publicaciones - libros

Computational alignment of a biopolymer sequence (e.g., an RNA or a protein) to a structure is an effective approach to predict and search for the structure of new sequences. To identify the structure of remote homologs, the structure-sequence alignment has to consider not only sequence similarity but also spatially conserved conformations caused by residue interactions, and consequently is computationally intractable. It is difficult to cope with the inefficiency without compromising alignment accuracy, especially for structure search in genomes or large databases. This paper introduces a novel method and a parameterized algorithm for structure-sequence alignment. Both the structure and the sequence are represented as graphs, where in general the graph for a biopolymer structure has a naturally small tree width. The algorithm constructs an optimal alignment by finding in the sequence graph the maximum valued subgraph isomorphic to the structure graph. It has the computational time complexity O ( k ^ t N ^2) for the structure of N residues and its tree decomposition of width t . The parameter k , small in nature, is determined by a statistical cutoff for the correspondence between the structure and the sequence. The paper demonstrates a successful application of the algorithm to developing a fast program for RNA structural homology search.

Protein design software places amino acid side chains by precomputing rotamer-pair energies and optimizing rotamer placement. If the software optimizes by rapid stochastic techniques, then the precomputation phase dominates run time. We present a new algorithm for rapid rotamer-pair energy computation that uses a trie data structure. The trie structure avoids redundant energy computations, and lends itself to time-saving pruning techniques based on a simple geometric criteria. With our new algorithm, we compute rotamer-pair energies nearly 4 times faster than the previous approach.

We present recent developments in efficiently maintaining the boundary and surface area of protein molecules as they undergo conformational changes. As the method that we devised keeps a highly accurate representation of the outer boundary surface and of the voids in the molecule, it can be useful in various applications, in particular in Monte Carlo Simulation. The current work continues and extends our previous work [10] and implements an efficient method for recalculating the surface area under conformational (and hence topological) changes based on techniques for efficient dynamic maintenance of graph connectivity. This method greatly improves the running time of our algorithm on most inputs, as we demonstrate in the experiments reported here.

The examination of the arrangement of the strands in beta-sandwich proteins reveals strict rules, which constrain the folding of a polypeptide chain. These structural rules allowed us to investigate the main principles of the packing of strands in the sandwich-like proteins and place severe restrictions on the number of allowed ways these proteins can fold. It was found that dissimilar sequences from different protein families and superfamilies, which share the same sandwich-like architecture, have 8 common key positions in sequences, whose residues govern the similar protein folding. These structural determinants can serve for protein classification.

Cryo-EM has become an increasingly powerful technique for elucidating the structure, dynamics and function of large flexible macromolecule assemblies that cannot be determined at atomic-resolution. A major challenge in analyzing EM maps of complexes is the identification of their subunits. We propose a fully automated highly efficient method for discovering high-resolution subunits of a complex, given as an intermediate resolution map, without prior knowledge of their boundaries and content. The method extracts helices from an EM map and uses their spatial arrangement to detect candidate subunits. The method was tested successfully on several simulated 8.0Å resolution maps. The obtained spatial helix arrangement was sufficient for the discovery of the correct subunits from a dataset of 887 SCOP representatives.