Pathway detection from protein interaction networks and gene expression data using color-coding methods and A? search algorithms.
Ontology highlight
ABSTRACT:
SUBMITTER: Yeh CY
PROVIDER: S-EPMC3346698 | biostudies-literature | 2012
REPOSITORIES: biostudies-literature
Publications
Pathway detection from protein interaction networks and gene expression data using color-coding methods and A∗ search algorithms.
Yeh Cheng-Yu CY Yeh Hsiang-Yuan HY Arias Carlos Roberto CR Soo Von-Wun VW
TheScientificWorldJournal 20120401
With the large availability of protein interaction networks and microarray data supported, to identify the linear paths that have biological significance in search of a potential pathway is a challenge issue. We proposed a color-coding method based on the characteristics of biological network topology and applied heuristic search to speed up color-coding method. In the experiments, we tested our methods by applying to two datasets: yeast and human prostate cancer networks and gene expression dat ...[more]
Similar Datasets
Project description:BackgroundProtein interactions are crucial components of all cellular processes. Recently, high-throughput methods have been developed to obtain a global description of the interactome (the whole network of protein interactions for a given organism). In 2002, the yeast interactome was estimated to contain up to 80,000 potential interactions. This estimate is based on the integration of data sets obtained by various methods (mass spectrometry, two-hybrid methods, genetic studies). High-throughput methods are known, however, to yield a non-negligible rate of false positives, and to miss a fraction of existing interactions. The interactome can be represented as a graph where nodes correspond with proteins and edges with pairwise interactions. In recent years clustering methods have been developed and applied in order to extract relevant modules from such graphs. These algorithms require the specification of parameters that may drastically affect the results. In this paper we present a comparative assessment of four algorithms: Markov Clustering (MCL), Restricted Neighborhood Search Clustering (RNSC), Super Paramagnetic Clustering (SPC), and Molecular Complex Detection (MCODE).ResultsA test graph was built on the basis of 220 complexes annotated in the MIPS database. To evaluate the robustness to false positives and false negatives, we derived 41 altered graphs by randomly removing edges from or adding edges to the test graph in various proportions. Each clustering algorithm was applied to these graphs with various parameter settings, and the clusters were compared with the annotated complexes. We analyzed the sensitivity of the algorithms to the parameters and determined their optimal parameter values. We also evaluated their robustness to alterations of the test graph. We then applied the four algorithms to six graphs obtained from high-throughput experiments and compared the resulting clusters with the annotated complexes.ConclusionThis analysis shows that MCL is remarkably robust to graph alterations. In the tests of robustness, RNSC is more sensitive to edge deletion but less sensitive to the use of suboptimal parameter values. The other two algorithms are clearly weaker under most conditions. The analysis of high-throughput data supports the superiority of MCL for the extraction of complexes from interaction networks.
| S-EPMC1637120 | biostudies-literature
Project description:Spectroradiometric satellite observations of the ocean are commonly referred to as "ocean color" remote sensing. NASA has continuously collected, processed, and distributed ocean color datasets since the launch of the Sea-viewing Wide-field-of-view Sensor (SeaWiFS) in 1997. While numerous ocean color algorithms have been developed in the past two decades that derive geophysical data products from sensor-observed radiometry, few papers have clearly demonstrated how to estimate measurement uncertainty in derived data products. As the uptake of ocean color data products continues to grow with the launch of new and advanced sensors, it is critical that pixel-by-pixel data product uncertainties are estimated during routine data processing. Knowledge of uncertainties can be used when studying long-term climate records, or to assist in the development and performance appraisal of bio-optical algorithms. In this methods paper we provide a comprehensive overview of how to formulate first-order first-moment (FOFM) calculus for propagating radiometric uncertainties through a selection of bio-optical models. We demonstrate FOFM uncertainty formulations for the following NASA ocean color data products: chlorophyll-a pigment concentration (Chl), the diffuse attenuation coefficient at 490 nm (K d,490), particulate organic carbon (POC), normalized fluorescent line height (nflh), and inherent optical properties (IOPs). Using a quality-controlled in situ hyperspectral remote sensing reflectance (R rs,i ) dataset, we show how computationally inexpensive, yet algebraically complex, FOFM calculations may be evaluated for correctness using the more computationally expensive Monte Carlo approach. We compare bio-optical product uncertainties derived using our test R rs dataset assuming spectrally-flat, uncorrelated relative uncertainties of 1, 5, and 10%. We also consider spectrally dependent, uncorrelated relative uncertainties in R rs . The importance of considering spectral covariances in R rs , where practicable, in the FOFM methodology is highlighted with an example SeaWiFS image. We also present a brief case study of two POC algorithms to illustrate how FOFM formulations may be used to construct measurement uncertainty budgets for ecologically-relevant data products. Such knowledge, even if rudimentary, may provide useful information to end-users when selecting data products or when developing their own algorithms.
| S-EPMC7344266 | biostudies-literature
Project description:BackgroundProtein-protein interaction networks are receiving increased attention due to their importance in understanding life at the cellular level. A major challenge in systems biology is to understand the modular structure of such biological networks. Although clustering techniques have been proposed for clustering protein-protein interaction networks, those techniques suffer from some drawbacks. The application of earlier clustering techniques to protein-protein interaction networks in order to predict protein complexes within the networks does not yield good results due to the small-world and power-law properties of these networks.ResultsIn this paper, we construct a new clustering algorithm for predicting protein complexes through the use of genetic algorithms. We design an objective function for exclusive clustering and overlapping clustering. We assess the quality of our proposed clustering algorithm using two gold-standard data sets.ConclusionsOur algorithm can identify protein complexes that are significantly enriched in the gold-standard data sets. Furthermore, our method surpasses three competing methods: MCL, ClusterOne, and MCODE in terms of the quality of the predicted complexes. The source code and accompanying examples are freely available at http://faculty.kfupm.edu.sa/ics/eramadan/GACluster.zip .
| S-EPMC4965715 | biostudies-literature
Project description:An approach to compare different peptide identification methods
2017-01-02 | PXD005118 | Pride
Project description:BackgroundCurrent experimental techniques, especially those applying liquid chromatography mass spectrometry, have made high-throughput proteomic studies possible. The increase in throughput however also raises concerns on the accuracy of identification or quantification. Most experimental procedures select in a given MS scan only a few relatively most intense parent ions, each to be fragmented (MS2) separately, and most other minor co-eluted peptides that have similar chromatographic retention times are ignored and their information lost.ResultsWe have computationally investigated the possibility of enhancing the information retrieval during a given LC/MS experiment by selecting the two or three most intense parent ions for simultaneous fragmentation. A set of spectra is created via superimposing a number of MS2 spectra, each can be identified by all search methods tested with high confidence, to mimick the spectra of co-eluted peptides. The generated convoluted spectra were used to evaluate the capability of several database search methods - SEQUEST, Mascot, X!Tandem, OMSSA, and RAId_DbS - in identifying true peptides from superimposed spectra of co-eluted peptides. We show that using these simulated spectra, all the database search methods will gain eventually in the number of true peptides identified by using the compound spectra of co-eluted peptides.Open peer reviewReviewed by Vlad Petyuk (nominated by Arcady Mushegian), King Jordan and Shamil Sunyaev. For the full reviews, please go to the Reviewers' comments section.
| S-EPMC2483259 | biostudies-literature
Project description:Many community detection algorithms have been developed to uncover the mesoscopic properties of complex networks. However how good an algorithm is, in terms of accuracy and computing time, remains still open. Testing algorithms on real-world network has certain restrictions which made their insights potentially biased: the networks are usually small, and the underlying communities are not defined objectively. In this study, we employ the Lancichinetti-Fortunato-Radicchi benchmark graph to test eight state-of-the-art algorithms. We quantify the accuracy using complementary measures and algorithms' computing time. Based on simple network properties and the aforementioned results, we provide guidelines that help to choose the most adequate community detection algorithm for a given network. Moreover, these rules allow uncovering limitations in the use of specific algorithms given macroscopic network properties. Our contribution is threefold: firstly, we provide actual techniques to determine which is the most suited algorithm in most circumstances based on observable properties of the network under consideration. Secondly, we use the mixing parameter as an easily measurable indicator of finding the ranges of reliability of the different algorithms. Finally, we study the dependency with network size focusing on both the algorithm's predicting power and the effective computing time.
| S-EPMC4967864 | biostudies-literature
Project description:BackgroundCommunity detection algorithms are fundamental tools to uncover important features in networks. There are several studies focused on social networks but only a few deal with biological networks. Directly or indirectly, most of the methods maximize modularity, a measure of the density of links within communities as compared to links between communities.ResultsHere we analyze six different community detection algorithms, namely, Combo, Conclude, Fast Greedy, Leading Eigen, Louvain and Spinglass, on two important biological networks to find their communities and evaluate the results in terms of topological and functional features through Kyoto Encyclopedia of Genes and Genomes pathway and Gene Ontology term enrichment analysis. At a high level, the main assessment criteria are 1) appropriate community size (neither too small nor too large), 2) representation within the community of only one or two broad biological functions, 3) most genes from the network belonging to a pathway should also belong to only one or two communities, and 4) performance speed. The first network in this study is a network of Protein-Protein Interactions (PPI) in Saccharomyces cerevisiae (Yeast) with 6532 nodes and 229,696 edges and the second is a network of PPI in Homo sapiens (Human) with 20,644 nodes and 241,008 edges. All six methods perform well, i.e., find reasonably sized and biologically interpretable communities, for the Yeast PPI network but the Conclude method does not find reasonably sized communities for the Human PPI network. Louvain method maximizes modularity by using an agglomerative approach, and is the fastest method for community detection. For the Yeast PPI network, the results of Spinglass method are most similar to the results of Louvain method with regard to the size of communities and core pathways they identify, whereas for the Human PPI network, Combo and Spinglass methods yield the most similar results, with Louvain being the next closest.ConclusionsFor Yeast and Human PPI networks, Louvain method is likely the best method to find communities in terms of detecting known core pathways in a reasonable time.
| S-EPMC6487005 | biostudies-literature
Project description:BackgroundIn recent times, the application of deoxyribonucleic acid (DNA) has diversified with the emergence of fields such as DNA computing and DNA data embedding. DNA data embedding, also known as DNA watermarking or DNA steganography, aims to develop robust algorithms for encoding non-genetic information in DNA. Inherently DNA is a digital medium whereby the nucleotide bases act as digital symbols, a fact which underpins all bioinformatics techniques, and which also makes trivial information encoding using DNA straightforward. However, the situation is more complex in methods which aim at embedding information in the genomes of living organisms. DNA is susceptible to mutations, which act as a noisy channel from the point of view of information encoded using DNA. This means that the DNA data embedding field is closely related to digital communications. Moreover it is a particularly unique digital communications area, because important biological constraints must be observed by all methods. Many DNA data embedding algorithms have been presented to date, all of which operate in one of two regions: non-coding DNA (ncDNA) or protein-coding DNA (pcDNA).ResultsThis paper proposes two novel DNA data embedding algorithms jointly called BioCode, which operate in ncDNA and pcDNA, respectively, and which comply fully with stricter biological restrictions. Existing methods comply with some elementary biological constraints, such as preserving protein translation in pcDNA. However there exist further biological restrictions which no DNA data embedding methods to date account for. Observing these constraints is key to increasing the biocompatibility and in turn, the robustness of information encoded in DNA.ConclusionThe algorithms encode information in near optimal ways from a coding point of view, as we demonstrate by means of theoretical and empirical (in silico) analyses. Also, they are shown to encode information in a robust way, such that mutations have isolated effects. Furthermore, the preservation of codon statistics, while achieving a near-optimum embedding rate, implies that BioCode pcDNA is also a near-optimum first-order steganographic method.
| S-EPMC3698116 | biostudies-literature
Project description:Frailty is a powerful prognostic tool in cirrhosis. Claims-based frailty scores estimate the presence of frailty without the need for in-person evaluation. These algorithms have not been validated in cirrhosis. Whether they measure true frailty or perform as well as frailty in outcome prediction is unknown. We evaluated 2 claims-based frailty scores-Hospital Frailty Risk Score (HFRS) and Claims-Based Frailty Index (CFI)-in 3 prospective cohorts comprising 1100 patients with cirrhosis. We assessed differences in neuromuscular/neurocognitive capabilities in those classified as frail or nonfrail based on each score. We assessed the ability of the indexes to discriminate frailty based on the Fried Frailty Index (FFI), chair stands, activities of daily living (ADL), and falls. Finally, we compared the performance of claims-based frailty measures and physical frailty measures to predict transplant-free survival using competing risk regression and patient-reported outcomes. The CFI identified neuromuscular deficits (balance, chair stands, hip strength), whereas the HFRS only identified poor chair-stand performance. The CFI had areas under the receiver operating characteristic curve (AUROCs) for identifying frailty as measured by the FFI, ADL, and falls of 0.57, 0.60, and 0.68, respectively; similarly, the AUROCs were 0.66, 0.63, and 0.67, respectively, for the HFRS. Claims-based frailty scores were associated with poor quality of life and sleep but were outperformed by the FFI and chair stands. The HFRS, per 10-point increase (but not the CFI) predicted survival of patients in the liver transplantation (subdistribution hazard ratio [SHR], 1.08; 95% confidence interval [CI], 1.03-1.12) and non-liver transplantation cohorts (SHR, 1.13; 95% CI, 1.05-1.22). Claims-based frailty scores do not adequately associate with physical frailty but are associated with important cirrhosis-related outcomes.
| S-EPMC8994168 | biostudies-literature
Project description:In this article, we report that in visual search, desaturated reddish targets are much easier to find than other desaturated targets, even when perceptual differences between targets and distractors are carefully equated. Observers searched for desaturated targets among mixtures of white and saturated distractors. Reaction times were hundreds of milliseconds faster for the most effective (reddish) targets than for the least effective (purplish) targets. The advantage for desaturated reds did not reflect an advantage for the lexical category "pink," because reaction times did not follow named color categories. Many pink stimuli were not found quickly, and many quickly found stimuli were not labeled "pink." Other possible explanations (e.g., linear-separability effects) also failed. Instead, we propose that guidance of visual search for desaturated colors is based on a combination of low-level color-opponent signals that is different from the combinations that produce perceived color. We speculate that this guidance might reflect a specialization for human skin.
| S-EPMC3050514 | biostudies-literature