31567164
Prediction of protein function using protein-protein interaction data
Assigning functions to novel proteins is one of the most important problems in the post-genomic era. We develop a novel approach that applies the theory of Markov random fields to infer a protein's functions using protein-protein interaction data and the functional annotations of its interaction protein partners. For each function of interest and a protein, we predict the probability that the protein has that function using Bayesian approaches. Unlike in other available approaches for protein annotation where a protein has or does not have a function of interest, we give a probability for having the function. This probability indicates how confident we are about the prediction. We apply our method to predict cellular functions (43 categories including a category "others") for yeast proteins defined in the Yeast Proteome Database, using the protein-protein interaction data from the Munich Information Center for Protein Sequences. We show that our approach outperforms other available methods for function prediction based on protein interaction data.
52802682
Inferring domain-domain interactions from protein-protein interactions
Protein-protein interactions are important events in cellular and biochemical processes within a cell. Several researchers have undertaken the task of analyzing protein-protein interactions covering all genes of an organism by using yeast two-hybrid assays. Protein-protein interactions involve physical interactions between protein domains. Therefore, understanding protein interactions at the domain level gives a global view of the protein interaction network, and possibly extends functions of proteins. In this study, we present a Maximum Likelihood approach to infer domain-domain interactions from the 5719 yeast protein-protein interactions obtained in the high throughput two-hybrid experiments by Uetz et al., 2000 and Ito et al., 2001. The accuracies of our predictions are measured at the protein level. Our study includes the following three results: (1) using the inferred domain-domain interactions, we predict interactions between proteins and achieve 39.0% specificity and 79.7% sensitivity; (2) our predicted protein-protein interactions have a significant overlap with the MIPS(http://mips.gfs.de) protein-protein interactions obtained by methods other than the two-hybrid systems; and (3) the mean correlation coefficient of the gene expression profiles for our predicted interacting pairs is significantly higher than that for random pairs as well as that of interacting pairs in Uetz's and Ito's experimental data. Our method has shown robustness in analyzing incomplete data sets and dealing with various experimental errors. We find several novel protein-protein interactions such as RPS0A interacting with APG17 and TAF40 interacting with SPT3, which are consistent with the functions of the proteins.
1201195
Prediction of Protein Function Using Protein-Protein Interaction Data
Assigning functions to novel proteins is one of the most important problems in the post-genomic era. Several approaches have been applied to this problem, including analyzing gene expression patterns, phylogenetic profiles, protein fusions and protein-protein interactions. We develop a novel approach that applies the theory of Markov random fields to infer a protein's functions using protein-protein interaction data and the functional annotations of its interaction protein partners. For each function of interest and a protein, we predict the probability that the protein has that function using Bayesian approaches. Unlike in other available approaches for protein annotation where a protein has or does not have a function of interest, we give a probability for having the function. This probability indicates how confident we are about the prediction. We apply our method to predict cellular functions (43 categories including a category "others") for yeast proteins defined in the Yeast Proteome Database (YPD), using the protein-protein interaction data from the Munich Information Center for Protein Sequences (MIPS, http://mips.gsf.de). We show that our approach outperforms other available methods for function prediction based on protein interaction data.
2822926
Sorting with Fixed-length Reversals
Abstract A popular puzzle TOP-SPIN consists of a permutation of 20 numbered disks on an oval track, with a turnstile capable of reversing a string of 4 consecutive disks. The goal is to sort the disks into identity permutation using reversals. We consider the more general case of sorting n element permutations with a turnstile of size k. The problem of computing the reversal distances is of considerable importance in reconstructing the evolutionary history of the genome. The minimum reversal sequence sorting the one genome to another corresponds to the most likely evolutionary path between them. We give a complete solution for all n and k, of the number of equivalence classes of n-permutations under k-reversal, for both permutations and circular permutations. We also prove the upper and lower bounds on the reversal distances between two permutations.
8315237
Local Lazy Regression: Making Use of the Neighborhood to Improve QSAR Predictions
Traditional quantitative structure-activity relationship (QSAR) models aim to capture global structure-activity trends present in a data set. In many situations, there may be groups of molecules which exhibit a specific set of features which relate to their activity or inactivity. Such a group of features can be said to represent a local structure-activity relationship. Traditional QSAR models may not recognize such local relationships. In this work, we investigate the use of local lazy regression (LLR), which obtains a prediction for a query molecule using its local neighborhood, rather than considering the whole data set. This modeling approach is especially useful for very large data sets because no a priori model need be built. We applied the technique to three biological data sets. In the first case, the root-mean-square error (RMSE) for an external prediction set was 0.94 log units versus 0.92 log units for the global model. However, LLR was able to characterize a specific group of anomalous molecules with much better accuracy (0.64 log units versus 0.70 log units for the global model). For the second data set, the LLR technique resulted in a decrease in RMSE from 0.36 log units to 0.31 log units for the external prediction set. In the third case, we obtained an RMSE of 2.01 log units versus 2.16 log units for the global model. In all cases, LLR led to a few observations being poorly predicted compared to the global model. We present an analysis of why this was observed and possible improvements to the local regression approach.
10712046
Algorithms for identifying protein cross-links via tandem mass spectrometry
Cross-linking technology combined with tandem mass spectrometry (MS-MS) is a powerful method that provides a rapid solution to the discovery of protein-protein interactions and protein structures. We studied the problem of detecting cross-linked peptides and cross-linked amino acids from tandem mass spectral data. Our method consists of two steps: the first step finds two protein subsequences whose mass sum equals a given mass measured from the mass spectrometry; and the second step finds the best cross-linked amino acids in these two peptide sequences that are optimally correlated to a given tandem mass spectrum. We designed fast and space-efficient algorithms for these two steps, and implemented and tested them on experimental data of cross-linked Hemoglobin proteins.
45055182
Mining frequent tree-like patterns in large datasets
Sequential pattern mining is crucial to data mining domains. This paper proposes a novel data mining approach for exploring hierarchical tree structures, named tree-like patterns, representing the relationships for a pair of items in a sequence. Using tree-like patterns, the relationships for a pair of items can be identified in terms of the cause and effect. A novel technique that efficiently counts support values for tree-like patterns using a queue structure is proposed. In addition, this paper addresses an efficient scheme for determining the frequency of a tree-like pattern in a sequence using a dynamic programming approach. Each tree-like pattern embedded in a sequence is considered to have a certain valuable meaning or the degree of importance used in different applications. Two addressed formulas are applied to determine the degree of significance for a specific sequence, which denotes the degree of consecutive items in a tree-like pattern for a sequence. The larger the degree of significance a tree-like pattern has, the more the tree-like pattern is compacted in the sequence. The characteristics differentiating the explored patterns from those obtained with other schemes are discussed. A simulation analysis of the proposed data mining approach is utilized to demonstrate its efficacy. Finally, the proposed approach is designed and implemented in a data mining system integrated into a novel e-learning platform.
44900435
Two test data selection strategies towards testing of Boolean specifications
Test data selection for software represented as Boolean formulae has not received much attention until the last decade. Most of the approaches are expression driven because generation of test cases is based on the Boolean formulae being tested. The paper discusses test data generation using a fault based approach in the sense that generation of test cases is based on particular types of faults occurring in the Boolean expression. Two special types of faults are considered. Moreover, two strategies of test case selection that guarantee the detection of these two types of faults are proposed.
1080835
Region Based Hidden Markov Random Field Model for Brain MR Image Segmentation
In this paper, we present the region based hidden Markov random field model (RBHMRF), which encodes the characteristics of different brain regions into a probabilistic framework for brain MR image segmentation. The recently proposed TV+L model is used for region extraction. By utilizing different spatial characteristics in different brain regions, the RMHMRF model performs beyond the current state-of-the-art method, the hidden Markov random field model (HMRF), which uses identical spatial information throughout the whole brain. Experiments on both real and synthetic 3D MR images show that the segmentation result of the proposed method has higher accuracy compared to existing algorithms. Keywords—Finite Gaussian mixture model, Hidden Markov random field model, image segmentation, MRI.
44631758
Agent-based forwarding strategies for reducing location management cost in mobile networks
A major issue with location management in mobile wireless networks is the high cost associated with location updates and searches. A search occurs when a caller needs to connect to a mobile user whose location is unknown to the caller and the network must locate the callee. An update occurs when a mobile user moves into a new registration area and the network is informed of the location change. We propose and analyze a class of new agent-based forwarding strategies with the objective to reduce the location management cost in mobile wireless networks. We develop analytical Markov models to compare the performance of the proposed strategies with existing location management schemes to demonstrate their feasibility and also to reveal conditions under which the proposed schemes are superior to existing ones.
18209709
Mesostructure from Specularity
We describe a simple and robust method for surface mesostructure acquisition. Our method builds on the observation that specular reflection is a reliable visual cue for surface mesostructure perception. In contrast to most photometric stereo methods, which take specularities as outliers and discard them, we propose a progressive acquisition system that captures a dense specularity field as the only information for mesostructure reconstruction. Our method can efficiently recover surfaces with fine-scale geometric details from complex real-world objects with a wide variety of reflection properties, including translucent, low albedo, and highly specular objects. We show results for a variety of objects including human skin, dried apricot, orange, jelly candy, black leather and dark chocolate.