30029896
Minimal-Risk Scoring Matrices for Sequence Analysis
We introduce a minimal-risk method for estimating the frequencies of amino acids at conserved positions in a protein family. Our method, called minimal-risk estimation, finds the optimal weighting between a set of observed amino acid counts and a set of pseudofrequencies, which represent prior information about the frequencies. We compute the optimal weighting by minimizing the expected distance between the estimated frequencies and the true population frequencies, measured by either a squared-error or a relative-entropy metric. Our method accounts for the source of the pseudofrequencies, which arise either from the background distribution of amino acids or from applying a substitution matrix to the observed data. Our frequency estimates therefore depend on the size and composition of the observed data as well as the source of the pseudofrequencies. We convert our frequency estimates into minimal-risk scoring matrices for sequence analysis. A large-scale cross-validation study, involving 48 variants of seven methods, shows that the best performing method is minimal-risk estimation using the squared-error metric. Our method is implemented in the package EMATRIX, which is available on the Internet at http://motif.stanford.edu/ematrix.
17812717
Discovering Empirically Conserved Amino Acid Substitution Groups in Databases of Protein Families
This paper introduces a method for identifying empirically conserved amino acid substitution groups. In contrast with existing approaches that view amino acid substitution as a pairwise phenomenon, the method presented here identifies conserved groups of amino acids using a data structure called a conditional distribution matrix. The conditional distribution matrix extends the concept of a pairwise substitution matrix by changing the context of substitution from a single amino acid to a group of amino acids. The matrix tabulates information from a database of protein families that contains numerous aligned positions. Each row in the matrix contains the distribution of amino acids in those aligned positions that contain a given conditioning group of amino acids. The method converts a database of protein families into a conditional distribution matrix and then examines each possible substitution group for evidence of conservation. The algorithm is applied to the BLOCKS and HSSP databases. Twenty amino acid substitution groups are found to be conserved empirically in both databases. These groups provide insight into biochemical properties that are conserved in protein evolution.
15119037
Modelling and heuristics of FMS scheduling with multiple objectives
The performance of a scheduling system, in practice, is not evaluated to satisfy a single objective, but to obtain a trade-off schedule regarding multiple objectives. Therefore, in this research, we make use of one of the multiple objective decision-making methods, a global criterion approach, to develop a multi-objective model for solving FMS scheduling problems with consideration of three performance measures, namely minimum mean job flow time, mean job tardiness, and minimum mean machine idle time, simultaneously. In addition, hybrid heuristics, which are a combination of two common local search methods, simulated annealing and tabu search, are also proposed for solving the addressed FMS scheduling problems. The feasibility and adaptability of the proposed heuristics are investigated through experimental results.