Unit-vector RMS (URMS) as a tool to analyze molecular dynamics trajectories

The Unit-vector RMS (URMS) is a new technique to compare protein chains and to detect similarities of chain segments. It is limited to comparison of C(alpha) chains. However, it has a number of unique features that include exceptionally weak dependence on the length of the chain and efficient detection of substructure similarities. Two molecular dynamics simulations of proteins in the neighborhood of their native states are used to test the performance of the URMS. The first simulation is of a solvated myoglobin and the second is of the protein MHC. In accord with previous studies the secondary structure elements (helices or sheets) are found to be moving relatively rigidly among flexible loops. In addition to these tests, folding trajectories of C peptides are analyzed, revealing a folding nucleus of seven amino acids.     

MOL3D,a modular and interactive program for molecular modeling and conformational analysis: I — basic modules

MOL3D is a generalized machine-independent computer program that lets the user interactively build 3D structures with different display options, such as wire, ball-and-stick and CPK representations. The program, which uses its own graphics package and driver, is designed to be very user friendly through the use of commands and menus. It has powerful transformation capabilities, such as software rotations, superpositions and zooming, and it is equipped with a fragment database that allows the user to build complex structures. The algorithm presented here is designed to perform computations in all the conformational space and therefore can be used to predict experimentally available quantities, such as NMR coupling constants. The program is efficient in the sense that it handles only dihedral angles in the first steps; as a result, it allows a rapid sampling of a great number of points through the entire conformational space. The user can choose between grid and Monte-Carlo searches of energy minimization, using a reasonable amount of computer time.     

SALAMI (Spectrum ALignments using high Accuracy Mass and hIgh sensitivity data): how to make the best out of hybrid MS/MS data

We present a software algorithm that combines ion trap and orbitrap product ion spectra acquired in parallel. The hybrid product ion spectra identify more peptides than when using two separate searches for the orbitrap and LTQ data. The program extracts the high-accuracy mass data from the Orbitrap mass analyzer and combines it with the high-sensitivity data analyzed in the LTQ linear ion trap; the m/z values of the high-confidence fragment ions are corrected to orbitrap mass accuracies and the fragment ion intensities are amplified. This approach utilizes the parallel spectrum measurement capabilities of the LTQ-Orbitrap. We present our approach to handling this type of hybrid data, explain our alignment program, and discuss the advantages of the chosen methodology.     

Knee joint secondary motion accuracy improved by quaternion-based optimizer with bony landmark constraints

Skin marker-based motion analysis has been widely used in biomechanical studies and clinical applications. Unfortunately, the accuracy of knee joint secondary motions is largely limited by the nonrigidity nature of human body segments. Numerous studies have investigated the characteristics of soft tissue movement. Utilizing these characteristics, we may improve the accuracy of knee joint motion measurement. An optimizer was developed by incorporating the soft tissue movement patterns at special bony landmarks into constraint functions. Bony landmark constraints were assigned to the skin markers at femur epicondyles, tibial plateau edges, and tibial tuberosity in a motion analysis algorithm by limiting their allowed position space relative to the underlying bone. The rotation matrix was represented by quaternion, and the constrained optimization problem was solved by Fletcher's version of the Levenberg-Marquardt optimization technique. The algorithm was validated by using motion data from both skin-based markers and bone-mounted markers attached to fresh cadavers. By comparing the results with the ground truth bone motion generated from the bone-mounted markers, the new algorithm had a significantly higher accuracy (root-mean-square (RMS) error: 0.7 ± 0.1 deg in axial rotation and 0.4 ± 0.1 deg in varus-valgus) in estimating the knee joint secondary rotations than algorithms without bony landmark constraints (RMS error: 1.7 ± 0.4 deg in axial rotation and 0.7 ± 0.1 deg in varus-valgus). Also, it predicts a more accurate medial-lateral translation (RMS error: 0.4 ± 0.1 mm) than the conventional techniques (RMS error: 1.2 ± 0.2 mm). The new algorithm, using bony landmark constrains, estimates more accurate secondary rotations and medial-lateral translation of the underlying bone.     

MINRMS: an efficient algorithm for determining protein structure similarity using root-mean-squared-distance

MOTIVATION: Existing algorithms for automated protein structure alignment generate contradictory results and are difficult to interpret. An algorithm which can provide a context for interpreting the alignment and uses a simple method to characterize protein structure similarity is needed. RESULTS: We describe a heuristic for limiting the search space for structure alignment comparisons between two proteins, and an algorithm for finding minimal root-mean-squared-distance (RMSD) alignments as a function of the number of matching residue pairs within this limited search space. Our alignment algorithm uses coordinates of alpha-carbon atoms to represent each amino acid residue and requires a total computation time of O(m(3) n(2)), where m and n denote the lengths of the protein sequences. This makes our method fast enough for comparisons of moderate-size proteins (fewer than approximately 800 residues) on current workstation-class computers and therefore addresses the need for a systematic analysis of multiple plausible shape similarities between two proteins using a widely accepted comparison metric.     

Accelerated Profile HMM Searches

Profile hidden Markov models (profile HMMs) and probabilistic inference methods have made important contributions to the theory of sequence database homology search. However, practical use of profile HMM methods has been hindered by the computational expense of existing software implementations. Here I describe an acceleration heuristic for profile HMMs, the "multiple segment Viterbi" (MSV) algorithm. The MSV algorithm computes an optimal sum of multiple ungapped local alignment segments using a striped vector-parallel approach previously described for fast Smith/Waterman alignment. MSV scores follow the same statistical distribution as gapped optimal local alignment scores, allowing rapid evaluation of significance of an MSV score and thus facilitating its use as a heuristic filter. I also describe a 20-fold acceleration of the standard profile HMM Forward/Backward algorithms using a method I call "sparse rescaling". These methods are assembled in a pipeline in which high-scoring MSV hits are passed on for reanalysis with the full HMM Forward/Backward algorithm. This accelerated pipeline is implemented in the freely available HMMER3 software package. Performance benchmarks show that the use of the heuristic MSV filter sacrifices negligible sensitivity compared to unaccelerated profile HMM searches. HMMER3 is substantially more sensitive and 100- to 1000-fold faster than HMMER2. HMMER3 is now about as fast as BLAST for protein searches.     

PROTDES: CHARMM toolbox for computational protein design

We present an open-source software able to automatically mutate any residue positions and find the best aminoacids in an arbitrary protein structure without requiring pairwise approximations. Our software, PROTDES, is based on CHARMM and it searches automatically for mutations optimizing a protein folding free energy. PROTDES allows the integration of molecular dynamics within the protein design. We have implemented an heuristic optimization algorithm that iteratively searches the best aminoacids and their conformations for an arbitrary set of positions within a structure. Our software allows CHARMM users to perform protein design calculations and to create their own procedures for protein design using their own energy functions. We show this by implementing three different energy functions based on different solvent treatments: surface area accessibility, generalized Born using molecular volume and an effective energy function. PROTDES, a tutorial, parameter sets, configuration tools and examples are freely available at http://soft.synth-bio.org/protdes.html.     

Polypeptide folding with off-lattice Monte Carlo dynamics: the method

The MC dynamics of an off-lattice all-atom protein backbone model with rigid amide planes are studied. The only degrees of freedom are the dihedral angle pairs of the C-atoms. Conformational changes are generated by Monte Carlo (MC) moves. The MC moves considered are single rotations (simple moves, SM's) giving rise to global conformational changes or, alternatively, cooperative rotations in a window of amide planes (window moves, WM's) generating local conformational changes in the window. Outside the window the protein conformation is kept invariant by constraints. These constraints produce a bias in the distribution of dihedral angles. The WM's are corrected for this bias by suitable Jacobians. The energy function used is derived from the CHARMM force field. In a first application to polyalanine it is demonstrated that WM's sample the conformational space more efficiently than SM's.Abbreviations CPU Central Processing Unit - MC Monte Carlo - MCD Monte Carlo Dynamics - MD Molecular Dynamics - RMS Root-Mean-Square - RMSD Root-Mean-Square-Deviation - SM Simple Move - WM Window Move     

Finding subtle motifs by branching from sample strings

Many motif finding algorithms apply local search techniques to a set of seeds. For example, GibbsDNA (Lawrence et al. 1993, Science, 262, 208-214) applies Gibbs sampling to random seeds, and MEME (Bailey and Elkan, 1994, Proceedings of the Second International Conference on Intelligent Systems for Molecular Biology (ISMB-94), 28-36) applies the EM algorithm to selected sample strings, i.e. substrings of the sample. In the case of subtle motifs, recent benchmarking efforts show that both random seeds and selected sample strings may never get close to the globally optimal motif. We propose a new approach which searches motif space by branching from sample strings, and implement this idea in both pattern-based and profile-based settings. Our PatternBranching and ProfileBranching algorithms achieve favorable results relative to other motif finding algorithms. Availability: http://www-cse.ucsd.edu/groups/bioinformatics/software.html     

Automatic detection of anchor points for multiple sequence alignment

Background  

Determining beforehand specific positions to align (anchor points) has proved valuable for the accuracy of automated multiple sequence alignment (MSA) software. This feature can be used manually to include biological expertise, or automatically, usually by pairwise similarity searches. Multiple local similarities are be expected to be more adequate, as more biologically relevant. However, even good multiple local similarities can prove incompatible with the ordering of an alignment.     

Ingeneue: a versatile tool for reconstituting genetic networks,with examples from the segment polarity network

Here we describe a software tool for synthesizing molecular genetic data into models of genetic networks. Our software program Ingeneue, written in Java, lets the user quickly turn a map of a genetic network into a dynamical model consisting of a set of ordinary differential equations. We developed Ingeneue as part of an ongoing effort to explore the design and evolvability of genetic networks. Ingeneue has three principal advantages over other available mathematical software: it automates instantiation of the same network model in each cell in a 2-D sheet of cells; it constructs model equations from pre-made building blocks corresponding to common biochemical processes; and it automates searches through parameter space, sensitivity analyses, and other common tasks. Here we discuss the structure of the software and some of the issues we have dealt with. We conclude with some examples of results we have achieved with Ingeneue for the Drosophila segment polarity network.     

Modeling and analysis of gene expression time-series based on co-expression

In this paper a novel approach is introduced for modeling and clustering gene expression time-series. The radial basis function neural networks have been used to produce a generalized and smooth characterization of the expression time-series. A co-expression coefficient is defined to evaluate the similarities of the models based on their temporal shapes and the distribution of the time points. The profiles are grouped using a fuzzy clustering algorithm incorporated with the proposed co-expression coefficient metric. The results on artificial and real data are presented to illustrate the advantages of the metric and method in grouping temporal profiles. The proposed metric has also been compared with the commonly used correlation coefficient under the same procedures and the results show that the proposed method produces better biologically relevant clusters.     

A software program for more reliable precursor ion assignation from LC-MS analysis using LTQ ultra zoom scan

We developed a software program (titled Precursor Ion Calibration software for LTQ or, in short, PICsL) that increases the reliability of precursor ion assignations from LC-MS analysis using ultra zoom scanning of LTQ linear ion trap MS and automatically corrects the assignations. Although existing software calculates the theoretical isotopic distribution according to m/z with a computational algorithm, our method simply searches for ions close to the theoretical mass value using both MS/MS raw data and Mascot search result files, followed by a second database search that identifies the proteins using the regenerated peak list files. Our software program mimics the manual inspection of the spectral data of precursor ions and is expected to be applicable not only for low resolution MS, such as LTQ, but also for a wide variety of MS instruments.     

Gapped spectral dictionaries and their applications for database searches of tandem mass spectra

Generating all plausible de novo interpretations of a peptide tandem mass (MS/MS) spectrum (Spectral Dictionary) and quickly matching them against the database represent a recently emerged alternative approach to peptide identification. However, the sizes of the Spectral Dictionaries quickly grow with the peptide length making their generation impractical for long peptides. We introduce Gapped Spectral Dictionaries (all plausible de novo interpretations with gaps) that can be easily generated for any peptide length thus addressing the limitation of the Spectral Dictionary approach. We show that Gapped Spectral Dictionaries are small thus opening a possibility of using them to speed-up MS/MS searches. Our MS-Gapped-Dictionary algorithm (based on Gapped Spectral Dictionaries) enables proteogenomics applications (such as searches in the six-frame translation of the human genome) that are prohibitively time consuming with existing approaches. MS-Gapped-Dictionary generates gapped peptides that occupy a niche between accurate but short peptide sequence tags and long but inaccurate full length peptide reconstructions. We show that, contrary to conventional wisdom, some high-quality spectra do not have good peptide sequence tags and introduce gapped tags that have advantages over the conventional peptide sequence tags in MS/MS database searches.     

IMPALA: matching a protein sequence against a collection of PSI-BLAST-constructed position-specific score matrices

MOTIVATION: Many studies have shown that database searches using position-specific score matrices (PSSMs) or profiles as queries are more effective at identifying distant protein relationships than are searches that use simple sequences as queries. One popular program for constructing a PSSM and comparing it with a database of sequences is Position-Specific Iterated BLAST (PSI-BLAST). RESULTS: This paper describes a new software package, IMPALA, designed for the complementary procedure of comparing a single query sequence with a database of PSI-BLAST-generated PSSMs. We illustrate the use of IMPALA to search a database of PSSMs for protein folds, and one for protein domains involved in signal transduction. IMPALA's sensitivity to distant biological relationships is very similar to that of PSI-BLAST. However, IMPALA employs a more refined analysis of statistical significance and, unlike PSI-BLAST, guarantees the output of the optimal local alignment by using the rigorous Smith-Waterman algorithm. Also, it is considerably faster when run with a large database of PSSMs than is BLAST or PSI-BLAST when run against the complete non-redundant protein database.     

Determining relevant features to recognize electron density patterns in x-ray protein crystallography

High-throughput computational methods in X-ray protein crystallography are indispensable to meet the goals of structural genomics. In particular, automated interpretation of electron density maps, especially those at mediocre resolution, can significantly speed up the protein structure determination process. TEXTAL(TM) is a software application that uses pattern recognition, case-based reasoning and nearest neighbor learning to produce reasonably refined molecular models, even with average quality data. In this work, we discuss a key issue to enable fast and accurate interpretation of typically noisy electron density data: what features should be used to characterize the density patterns, and how relevant are they? We discuss the challenges of constructing features in this domain, and describe SLIDER, an algorithm to determine the weights of these features. SLIDER searches a space of weights using ranking of matching patterns (relative to mismatching ones) as its evaluation function. Exhaustive search being intractable, SLIDER adopts a greedy approach that judiciously restricts the search space only to weight values that cause the ranking of good matches to change. We show that SLIDER contributes significantly in finding the similarity between density patterns, and discuss the sensitivity of feature relevance to the underlying similarity metric.     

Three-dimensional, sequence order-independent structural comparison of a serine protease against the crystallographic database reveals active site similarities: potential implications to evolution and to protein folding.

We have recently developed a fast approach to comparisons of 3-dimensional structures. Our method is unique, treating protein structures as collections of unconnected points (atoms) in space. It is completely independent of the amino acid sequence order. It is unconstrained by insertions, deletions, and chain directionality. It matches single, isolated amino acids between 2 different structures strictly by their spatial positioning regardless of their relative sequential position in the amino acid chain. It automatically detects a recurring 3D motif in protein molecules. No predefinition of the motif is required. The motif can be either in the interior of the proteins or on their surfaces. In this work, we describe an enhancement over our previously developed technique, which considerably reduces the complexity of the algorithm. This results in an extremely fast technique. A typical pairwise comparison of 2 protein molecules requires less than 3 s on a workstation. We have scanned the structural database with dozens of probes, successfully detecting structures that are similar to the probe. To illustrate the power of this method, we compare the structure of a trypsin-like serine protease against the structural database. Besides detecting homologous trypsin-like proteases, we automatically obtain 3D, sequence order-independent, active-site similarities with subtilisin-like and sulfhydryl proteases. These similarities equivalence isolated residues, not conserving the linear order of the amino acids in the chains. The active-site similarities are well known and have been detected by manually inspecting the structures in a time-consuming, laborious procedure. This is the first time such equivalences are obtained automatically from the comparison of full structures. The far-reaching advantages and the implications of our novel algorithm to studies of protein folding, to evolution, and to searches for pharmacophoric patterns are discussed.     

Spectrum-to-spectrum searching using a proteome-wide spectral library

The unambiguous assignment of tandem mass spectra (MS/MS) to peptide sequences remains a key unsolved problem in proteomics. Spectral library search strategies have emerged as a promising alternative for peptide identification, in which MS/MS spectra are directly compared against a reference library of confidently assigned spectra. Two problems relate to library size. First, reference spectral libraries are limited to rediscovery of previously identified peptides and are not applicable to new peptides, because of their incomplete coverage of the human proteome. Second, problems arise when searching a spectral library the size of the entire human proteome. We observed that traditional dot product scoring methods do not scale well with spectral library size, showing reduction in sensitivity when library size is increased. We show that this problem can be addressed by optimizing scoring metrics for spectrum-to-spectrum searches with large spectral libraries. MS/MS spectra for the 1.3 million predicted tryptic peptides in the human proteome are simulated using a kinetic fragmentation model (MassAnalyzer version2.1) to create a proteome-wide simulated spectral library. Searches of the simulated library increase MS/MS assignments by 24% compared with Mascot, when using probabilistic and rank based scoring methods. The proteome-wide coverage of the simulated library leads to 11% increase in unique peptide assignments, compared with parallel searches of a reference spectral library. Further improvement is attained when reference spectra and simulated spectra are combined into a hybrid spectral library, yielding 52% increased MS/MS assignments compared with Mascot searches. Our study demonstrates the advantages of using probabilistic and rank based scores to improve performance of spectrum-to-spectrum search strategies.     

Effective detection of remote homologues by searching in sequence dataset of a protein domain fold

Profile matching methods are commonly used in searches in protein sequence databases to detect evolutionary relationships. We describe here a sensitive protocol, which detects remote similarities by searching in a specialized database of sequences belonging to a fold. We have assessed this protocol by exploring the relationships we detect among sequences known to belong to specific folds. We find that searches within sequences adopting a fold are more effective in detecting remote similarities and evolutionary connections than searches in a database of all sequences. We also discuss the implications of using this strategy to link sequence and structure space.     

Multiple structure alignment and consensus identification for proteins

Background  

An algorithm is presented to compute a multiple structure alignment for a set of proteins and to generate a consensus (pseudo) protein which captures common substructures present in the given proteins. The algorithm represents each protein as a sequence of triples of coordinates of the alpha-carbon atoms along the backbone. It then computes iteratively a sequence of transformation matrices (i.e., translations and rotations) to align the proteins in space and generate the consensus. The algorithm is a heuristic in that it computes an approximation to the optimal alignment that minimizes the sum of the pairwise distances between the consensus and the transformed proteins.