Algorithms for Finding Small Attractors in Boolean Networks

A Boolean network is a model used to study the interactions between different genes in genetic regulatory networks. In this paper, we present several algorithms using gene ordering and feedback vertex sets to identify singleton attractors and small attractors in Boolean networks. We analyze the average case time complexities of some of the proposed algorithms. For instance, it is shown that the outdegree-based ordering algorithm for finding singleton attractors works in time for , which is much faster than the naive time algorithm, where is the number of genes and is the maximum indegree. We performed extensive computational experiments on these algorithms, which resulted in good agreement with theoretical results. In contrast, we give a simple and complete proof for showing that finding an attractor with the shortest period is NP-hard.[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32]     

Analysis of Free Energy Signals Arising from Nucleotide Hybridization Between rRNA and mRNA Sequences during Translation in Eubacteria

A decoding algorithm is tested that mechanistically models the progressive alignments that arise as the mRNA moves past the rRNA tail during translation elongation. Each of these alignments provides an opportunity for hybridization between the single-stranded, -terminal nucleotides of the 16S rRNA and the spatially accessible window of mRNA sequence, from which a free energy value can be calculated. Using this algorithm we show that a periodic, energetic pattern of frequency 1/3 is revealed. This periodic signal exists in the majority of coding regions of eubacterial genes, but not in the non-coding regions encoding the 16S and 23S rRNAs. Signal analysis reveals that the population of coding regions of each bacterial species has a mean phase that is correlated in a statistically significant way with species () content. These results suggest that the periodic signal could function as a synchronization signal for the maintenance of reading frame and that codon usage provides a mechanism for manipulation of signal phase.[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32]     

Splitting the BLOSUM Score into Numbers of Biological Significance

Mathematical tools developed in the context of Shannon information theory were used to analyze the meaning of the BLOSUM score, which was split into three components termed as the BLOSUM spectrum (or BLOSpectrum). These relate respectively to the sequence convergence (the stochastic similarity of the two protein sequences), to the background frequency divergence (typicality of the amino acid probability distribution in each sequence), and to the target frequency divergence (compliance of the amino acid variations between the two sequences to the protein model implicit in the BLOCKS database). This treatment sharpens the protein sequence comparison, providing a rationale for the biological significance of the obtained score, and helps to identify weakly related sequences. Moreover, the BLOSpectrum can guide the choice of the most appropriate scoring matrix, tailoring it to the evolutionary divergence associated with the two sequences, or indicate if a compositionally adjusted matrix could perform better.[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29]     

Multipattern Consensus Regions in Multiple Aligned Protein Sequences and Their Segmentation

Decomposing a biological sequence into its functional regions is an important prerequisite to understand the molecule. Using the multiple alignments of the sequences, we evaluate a segmentation based on the type of statistical variation pattern from each of the aligned sites. To describe such a more general pattern, we introduce multipattern consensus regions as segmented regions based on conserved as well as interdependent patterns. Thus the proposed consensus region considers patterns that are statistically significant and extends a local neighborhood. To show its relevance in protein sequence analysis, a cancer suppressor gene called p53 is examined. The results show significant associations between the detected regions and tendency of mutations, location on the 3D structure, and cancer hereditable factors that can be inferred from human twin studies.[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27]     

Targeted Proteomics to Assess the Response to Anti-Angiogenic Treatment in Human Glioblastoma (GBM)

Glioblastoma (GBM) is a highly aggressive primary brain tumor with dismal outcome for affected patients. Because of the significant neo-angiogenesis exhibited by GBMs, anti-angiogenic therapies have been intensively evaluated during the past years. Recent clinical studies were however disappointing, although a subpopulation of patients may benefit from such treatment. We have previously shown that anti-angiogenic targeting in GBM increases hypoxia and leads to a metabolic adaptation toward glycolysis, suggesting that combination treatments also targeting the glycolytic phenotype may be effective in GBM patients. The aim of this study was to identify marker proteins that are altered by treatment and may serve as a short term readout of anti-angiogenic therapy. Ultimately such proteins could be tested as markers of efficacy able to identify patient subpopulations responsive to the treatment. We applied a proteomics approach based on selected reaction monitoring (SRM) to precisely quantify targeted protein candidates, selected from pathways related to metabolism, apoptosis and angiogenesis. The workflow was developed in the context of patient-derived intracranial GBM xenografts developed in rodents and ensured the specific identification of human tumor versus rodent stroma-derived proteins. Quality control experiments were applied to assess sample heterogeneity and reproducibility of SRM assays at different levels. The data demonstrate that tumor specific proteins can be precisely quantified within complex biological samples, reliably identifying small concentration differences induced by the treatment. In line with previous work, we identified decreased levels of TCA cycle enzymes, including isocitrate dehydrogenase, whereas malectin, calnexin, and lactate dehydrogenase A were augmented after treatment. We propose the most responsive proteins of our subset as potential novel biomarkers to assess treatment response after anti-angiogenic therapy that warrant future analysis in clinical GBM samples.In the context of glioblastoma (GBM)¹, the quest for effective biomarkers is vital given that GBM is the most aggressive primary brain tumor in adults and no curative treatment is currently available (1). GBM is characterized by extensive invasion into the brain parenchyma, a high proliferation rate, neo-angiogenesis and significant cellular and molecular heterogeneity. Current treatment involves neurosurgery, radiotherapy and chemotherapy, yet the median life expectancy of affected patients is less than fifteen months. Recent efforts have focused on targeting the vascular endothelial growth factor (VEGF) system which is critical for tumor angiogenesis, however GBM quickly develop escape mechanisms leading to tumor progression (2, 3). Previous work from our group demonstrated that GBMs adapt to anti-VEGF treatment via a metabolic switch in tumor cells toward increased glycolysis (4, 5). This was accompanied by increased hypoxia and tumor cell invasion, with little or no effect on tumor growth (4). In agreement with these preclinical studies, two large scale clinical trials addressing the impact of bevacizumab, a VEGF targeting antibody, in newly diagnosed GBM patients reported disappointing results: although progression free survival appeared to be improved, no effect on overall survival was observed (6, 7). The evaluation of such studies are complicated by the fact that anti-angiogenic agents affect blood vessel permeability thereby directly modulating neuroimaging parameters used to determine treatment effects (8, 9). Thus there is a need for molecular biomarkers to adequately determine treatment response to anti-angiogenic agents.MS-based proteomics (10, 11) is widely used in the field of cancer research in particular in the context of biomarker development including discovery and verification. The application of the selected reaction monitoring (SRM) approach to proteomics reinforced the importance of MS in biomarker development (12–14). Indeed, SRM is a targeted proteomics approach that allows a precise and absolute quantification of previously selected marker candidates (15, 16). Moreover it can be applied in a supervised discovery phase for potential biomarkers (17, 18), i.e. the precise quantification of a wider range of selected biomarkers of interest by the use of stable isotope labeled (SIL) peptides in crude quality. Because of its high selectivity, sensitivity and accuracy, SRM, also named multiple reaction monitoring (MRM), is currently the reference method in targeted proteomics (14, 19).The aim of this study was to identify proteins that are altered by anti-angiogenic treatment, thereby providing biomolecular signatures of tumor response in GBM. Ultimately such protein markers could be evaluated for their utility as markers of efficacy that allow to discriminate responders from nonresponders. The study was focused on target proteins that may exhibit significant differences in protein expression reflecting the metabolic switch exhibited during anti-angiogenic therapy. An SRM workflow designed on a triple quadrupole platform (20), was developed and optimized in the context of GBM xenografts treated with bevacizumab in order to perform, in a supervised manner, a precise relative quantification of target proteins. We have previously shown that patient derived GBM xenografts developed in rodents faithfully reflect human pathology and allow a detailed analysis of the tumor and stromal compartments (4, 21–24). Furthermore xenograft models facilitate the access to control samples as well as the possibility of controlled interventional studies (25). The results presented herein demonstrate the feasibility of SRM to precisely quantify small changes in protein concentration after treatment. We highlight the importance of peptide selection, data normalization and consideration of the variability of target proteins within complex biological samples before assessing their concentration changes in subsequent comparative studies. From an initial set of 100 candidates, we screened 74 proteins and identified 32 responsive to anti-angiogenic treatment. We propose malectin, calnexin, lactate dehydrogenase A (LDHA), and isocitrate dehydrogenase (IDH) as novel response markers to anti-angiogenic therapy.     

The Wavelet-Based Cluster Analysis for Temporal Gene Expression Data

A variety of high-throughput methods have made it possible to generate detailed temporal expression data for a single gene or large numbers of genes. Common methods for analysis of these large data sets can be problematic. One challenge is the comparison of temporal expression data obtained from different growth conditions where the patterns of expression may be shifted in time. We propose the use of wavelet analysis to transform the data obtained under different growth conditions to permit comparison of expression patterns from experiments that have time shifts or delays. We demonstrate this approach using detailed temporal data for a single bacterial gene obtained under 72 different growth conditions. This general strategy can be applied in the analysis of data sets of thousands of genes under different conditions.[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29]     

Question Processing and Clustering in INDOC: A Biomedical Question Answering System

The exponential growth in the volume of publications in the biomedical domain has made it impossible for an individual to keep pace with the advances. Even though evidence-based medicine has gained wide acceptance, the physicians are unable to access the relevant information in the required time, leaving most of the questions unanswered. This accentuates the need for fast and accurate biomedical question answering systems. In this paper we introduce INDOC—a biomedical question answering system based on novel ideas of indexing and extracting the answer to the questions posed. INDOC displays the results in clusters to help the user arrive the most relevant set of documents quickly. Evaluation was done against the standard OHSUMED test collection. Our system achieves high accuracy and minimizes user effort.[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24]     

Proinsulin and the Genetics of Diabetes Mellitus

Insulin plays a central role in the regulation of vertebrate metabolism. The hormone, the post-translational product of a single-chain precursor, is a globular protein containing two chains, A (21 residues) and B (30 residues). Recent advances in human genetics have identified dominant mutations in the insulin gene causing permanent neonatal-onset DM² (1–4). The mutations are predicted to block folding of the precursor in the ER of pancreatic β-cells. Although expression of the wild-type allele would in other circumstances be sufficient to maintain homeostasis, studies of a corresponding mouse model (5–7) suggest that the misfolded variant perturbs wild-type biosynthesis (8, 9). Impaired β-cell secretion is associated with ER stress, distorted organelle architecture, and cell death (10). These findings have renewed interest in insulin biosynthesis (11–13) and the structural basis of disulfide pairing (14–19). Protein evolution is constrained not only by structure and function but also by susceptibility to toxic misfolding.Insulin plays a central role in the regulation of vertebrate metabolism. The hormone, the post-translational product of a single-chain precursor, is a globular protein containing two chains, A (21 residues) and B (30 residues). Recent advances in human genetics have identified dominant mutations in the insulin gene causing permanent neonatal-onset DM² (1–4). The mutations are predicted to block folding of the precursor in the ER of pancreatic β-cells. Although expression of the wild-type allele would in other circumstances be sufficient to maintain homeostasis, studies of a corresponding mouse model (5–7) suggest that the misfolded variant perturbs wild-type biosynthesis (8, 9). Impaired β-cell secretion is associated with ER stress, distorted organelle architecture, and cell death (10). These findings have renewed interest in insulin biosynthesis (11–13) and the structural basis of disulfide pairing (14–19). Protein evolution is constrained not only by structure and function but also by susceptibility to toxic misfolding.     

A Pipeline for Determining Protein–Protein Interactions and Proximities in the Cellular Milieu

It remains extraordinarily challenging to elucidate endogenous protein-protein interactions and proximities within the cellular milieu. The dynamic nature and the large range of affinities of these interactions augment the difficulty of this undertaking. Among the most useful tools for extracting such information are those based on affinity capture of target bait proteins in combination with mass spectrometric readout of the co-isolated species. Although highly enabling, the utility of affinity-based methods is generally limited by difficulties in distinguishing specific from nonspecific interactors, preserving and isolating all unique interactions including those that are weak, transient, or rapidly exchanging, and differentiating proximal interactions from those that are more distal. Here, we have devised and optimized a set of methods to address these challenges. The resulting pipeline involves flash-freezing cells in liquid nitrogen to preserve the cellular environment at the moment of freezing; cryomilling to fracture the frozen cells into intact micron chunks to allow for rapid access of a chemical reagent and to stabilize the intact endogenous subcellular assemblies and interactors upon thawing; and utilizing the high reactivity of glutaraldehyde to achieve sufficiently rapid stabilization at low temperatures to preserve native cellular interactions. In the course of this work, we determined that relatively low molar ratios of glutaraldehyde to reactive amines within the cellular milieu were sufficient to preserve even labile and transient interactions. This mild treatment enables efficient and rapid affinity capture of the protein assemblies of interest under nondenaturing conditions, followed by bottom-up MS to identify and quantify the protein constituents. For convenience, we have termed this approach Stabilized Affinity Capture Mass Spectrometry. Here, we demonstrate that Stabilized Affinity Capture Mass Spectrometry allows us to stabilize and elucidate local, distant, and transient protein interactions within complex cellular milieux, many of which are not observed in the absence of chemical stabilization.Insights into many cellular processes require detailed information about interactions between the participating proteins. However, the analysis of such interactions can be challenging because of the often-diverse physicochemical properties and the abundances of the constituent proteins, as well as the sometimes wide range of affinities and complex dynamics of the interactions. One of the key challenges has been acquiring information concerning transient, low affinity interactions in highly complex cellular milieux (3, 4).Methods that allow elucidation of such information include co-localization microscopy (5), fluorescence protein Förster resonance energy transfer (4), immunoelectron microscopy (5), yeast two-hybrid (6), and affinity capture (7, 8). Among these, affinity capture (AC)¹ has the unique potential to detect all specific in vivo interactions simultaneously, including those that interact both directly and indirectly. In recent times, the efficacy of such affinity isolation experiments has been greatly enhanced through the use of sensitive modern mass spectrometric protein identification techniques (9). Nevertheless, AC suffers from several shortcomings. These include the problem of 1) distinguishing specific from nonspecific interactors (10, 11); 2) preserving and isolating all unique interactions including those that are weak and/or transient, as well as those that exchange rapidly (10, 12, 13); and 3) differentiating proximal from more distant interactions (14).We describe here an approach to address these issues, which makes use of chemical stabilization of protein assemblies in the complex cellular milieu prior to AC. Chemical stabilization is an emerging technique for stabilizing and elucidating protein associations both in vitro (15–20) and in vivo (3, 12, 14, 21–29), with mass spectrometric (MS) readout of the AC proteins and their connectivities. Such chemical stabilization methods are indeed well-established and are often used in electron microscopy for preserving complexes and subcellular structures both in the cellular milieu (3) and in purified complexes (30, 31), wherein the most reliable, stable, and established stabilization reagents is glutaraldehyde. Recently, glutaraldehyde has been applied in the “GraFix” protocol in which purified protein complexes are subjected to centrifugation through a density gradient that also contains a gradient of glutaraldehyde (30, 31), allowing for optimal stabilization of authentic complexes and minimization of nonspecific associations and aggregation. GraFix has also been combined with mass spectrometry on purified complexes bound to EM grids to obtain a compositional analysis of the complexes (32), thereby raising the possibility that glutaraldehyde can be successfully utilized in conjunction with AC in complex cellular milieux directly.In this work, we present a robust pipeline for determining specific protein-protein interactions and proximities from cellular milieux. The first steps of the pipeline involve the well-established techniques of flash freezing the cells of interest in liquid nitrogen and cryomilling, which have been known for over a decade (33, 34) to preserve the cellular environment, as well as having shown outstanding performance when used in analysis of macromolecular interactions in yeast (35–39), bacterial (40, 41), trypanosome (42), mouse (43), and human (44–47) systems. The resulting frozen powder, composed of intact micron chunks of cells that have great surface area and outstanding solvent accessibility, is well suited for rapid low temperature chemical stabilization using glutaraldehyde. We selected glutaraldehyde for our procedure based on the fact that it is a very reactive stabilizing reagent, even at lower temperatures, and because it has already been shown to stabilize enzymes in their functional state (48–50). We employed highly efficient, rapid, single stage affinity capture (36, 51) for isolation and bottom-up MS for analysis of the macromolecular assemblies of interest (52–54). For convenience, we have termed this approach Stabilized Affinity-Capture Mass Spectrometry (SAC-MS).