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]     

Identification of Tumor-associated Autoantigens for the Diagnosis of Colorectal Cancer in Serum Using High Density Protein Microarrays

There is a mounting evidence of the existence of autoantibodies associated to cancer progression. Antibodies are the target of choice for serum screening because of their stability and suitability for sensitive immunoassays. By using commercial protein microarrays containing 8000 human proteins, we examined 20 sera from colorectal cancer (CRC) patients and healthy subjects to identify autoantibody patterns and associated antigens. Forty-three proteins were differentially recognized by tumoral and reference sera (p value <0.04) in the protein microarrays. Five immunoreactive antigens, PIM1, MAPKAPK3, STK4, SRC, and FGFR4, showed the highest prevalence in cancer samples, whereas ACVR2B was more abundant in normal sera. Three of them, PIM1, MAPKAPK3, and ACVR2B, were used for further validation. A significant increase in the expression level of these antigens on CRC cell lines and colonic mucosa was confirmed by immunoblotting and immunohistochemistry on tissue microarrays. A diagnostic ELISA based on the combination of MAPKAPK3 and ACVR2B proteins yielded specificity and sensitivity values of 73.9 and 83.3% (area under the curve, 0.85), respectively, for CRC discrimination after using an independent sample set containing 94 sera representative of different stages of progression and control subjects. In summary, these studies confirmed the presence of specific autoantibodies for CRC and revealed new individual markers of disease (PIM1, MAPKAPK3, and ACVR2B) with the potential to diagnose CRC with higher specificity and sensitivity than previously reported serum biomarkers.Colorectal cancer (CRC)¹ is the second most prevalent cancer in the western world. The development of this disease takes decades and involves multiple genetic events. CRC remains a major cause of mortality in developed countries because most of the patients are diagnosed at advanced stages because of the reluctance to use highly invasive diagnostic tools like colonoscopy. Actually only a few proteins have been described as biomarkers in CRC (carcinoembryonic antigen (CEA), CA19.9, and CA125 (1–3)), although none of them is recommended for clinical screening (4). Proteomics analysis is actively used for the identification of new biomarkers. In previous studies, the use of two-dimensional DIGE and antibody microarrays allowed the identification of differentially expressed proteins in CRC tissue, including isoforms and post-translational modifications responsible for modifications in signaling pathways (5–8). Both approaches resulted in the identification of a collection of potential tumoral tissue biomarkers that is currently being investigated.However, the implementation of simpler, non-invasive methods for the early detection of CRC should be based on the identification of proteins or antibodies in serum or plasma (9–13). There is ample evidence of the existence of an immune response to cancer in humans as demonstrated by the presence of autoantibodies in cancer sera. Self-proteins (autoantigens) altered before or during tumor formation can elicit an immune response (13–19). These tumor-specific autoantibodies can be detected at early cancer stages and prior to cancer diagnosis revealing a great potential as biomarkers (14, 15, 20). Tumor proteins can be affected by specific point mutations, misfolding, overexpression, aberrant glycosylation, truncation, or aberrant degradation (e.g. p53, HER2, NY-ESO1, or MUC1 (16, 21–25)). In fact, a number of tumor-associated autoantigens (TAAs) were identified previously in different studies involving autoantibody screening in CRC (26–28).Several approaches have been used to identify TAAs in cancer, including natural protein arrays prepared with fractions obtained from two-dimensional LC separations of tumoral samples (29, 30) or protein extracts from cancer cells or tissue (9, 31) probed by Western blot with patient sera, cancer tissue peptide libraries expressed as cDNA expression libraries for serological screening (serological analysis of recombinant cDNA expression libraries (SEREX)) (22, 32), or peptides expressed on the surface of phages in combination with microarrays (17, 18, 33, 34). However, these approaches suffer from several drawbacks. In some cases TAAs have to be isolated and identified from the reactive protein lysate by LC-MS techniques, or in the phage display approach, the reactive TAA could be a mimotope without a corresponding linear amino acid sequence. Moreover, cDNA libraries might not be representative of the protein expression levels in tumors as there is a poor correspondence between mRNA and protein levels.Protein arrays provide a novel platform for the identification of both autoantibodies and their respective TAAs for diagnostic purposes in cancer serum patients. They present some advantages. Proteins printed on the microarray are known “a priori,” avoiding the need for later identifications and the discovery of mimotopes. There is no bias in protein selection as the proteins are printed at a similar concentration. This should result in a higher sensitivity for biomarker identification (13, 35, 36).In this study, we used commercially available high density protein microarrays for the identification of autoantibody signatures and tumor-associated antigens in colorectal cancer. We screened 20 CRC patient and control sera with protein microarrays containing 8000 human proteins to identify the CRC-associated autoantibody repertoire and the corresponding TAAs. Autoantibody profiles that discriminated the different types of CRC metastasis were identified. Moreover a set of TAAs showing increased or decreased expression in cancer cell lines and paired tumoral tissues was found. Finally an ELISA was set up to test the ability of the most immunoreactive proteins to detect colorectal adenocarcinoma. On the basis of the antibody response, combinations of three antigens, PIM1, MAPKAPK3, and ACVR2B, showed a great potential for diagnosis.     

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]     

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]     

Vinyl Sulfones as Antiparasitic Agents and a Structural Basis for Drug Design

Cysteine proteases of the papain superfamily are implicated in a number of cellular processes and are important virulence factors in the pathogenesis of parasitic disease. These enzymes have therefore emerged as promising targets for antiparasitic drugs. We report the crystal structures of three major parasite cysteine proteases, cruzain, falcipain-3, and the first reported structure of rhodesain, in complex with a class of potent, small molecule, cysteine protease inhibitors, the vinyl sulfones. These data, in conjunction with comparative inhibition kinetics, provide insight into the molecular mechanisms that drive cysteine protease inhibition by vinyl sulfones, the binding specificity of these important proteases and the potential of vinyl sulfones as antiparasitic drugs.Sleeping sickness (African trypanosomiasis), caused by Trypanosoma brucei, and malaria, caused by Plasmodium falciparum, are significant, parasitic diseases of sub-Saharan Africa (1). Chagas'' disease (South American trypanosomiasis), caused by Trypanosoma cruzi, affects approximately, 16–18 million people in South and Central America. For all three of these protozoan diseases, resistance and toxicity to current therapies makes treatment increasingly problematic, and thus the development of new drugs is an important priority (2–4).T. cruzi, T. brucei, and P. falciparum produce an array of potential target enzymes implicated in pathogenesis and host cell invasion, including a number of essential and closely related papain-family cysteine proteases (5, 6). Inhibitors of cruzain and rhodesain, major cathepsin L-like papain-family cysteine proteases of T. cruzi and T. brucei rhodesiense (7–10) display considerable antitrypanosomal activity (11, 12), and some classes have been shown to cure T. cruzi infection in mouse models (11, 13, 14).In P. falciparum, the papain-family cysteine proteases falcipain-2 (FP-2)⁶ and falcipain-3 (FP-3) are known to catalyze the proteolysis of host hemoglobin, a process that is essential for the development of erythrocytic parasites (15–17). Specific inhibitors, targeted to both enzymes, display antiplasmodial activity (18). However, although the abnormal phenotype of FP-2 knock-outs is “rescued” during later stages of trophozoite development (17), FP-3 has proved recalcitrant to gene knock-out (16) suggesting a critical function for this enzyme and underscoring its potential as a drug target.Sequence analyses and substrate profiling identify cruzain, rhodesain, and FP-3 as cathepsin L-like, and several studies describe classes of small molecule inhibitors that target multiple cathepsin L-like cysteine proteases, some with overlapping antiparasitic activity (19–22). Among these small molecules, vinyl sulfones have been shown to be effective inhibitors of a number of papain family-like cysteine proteases (19, 23–27). Vinyl sulfones have many desirable attributes, including selectivity for cysteine proteases over serine proteases, stable inactivation of the target enzyme, and relative inertness in the absence of the protease target active site (25). This class has also been shown to have desirable pharmacokinetic and safety profiles in rodents, dogs, and primates (28, 29). We have determined the crystal structures of cruzain, rhodesain, and FP-3 bound to vinyl sulfone inhibitors and performed inhibition kinetics for each enzyme. Our results highlight key areas of interaction between proteases and inhibitors. These results help validate the vinyl sulfones as a class of antiparasitic drugs and provide structural insights to facilitate the design or modification of other small molecule inhibitor scaffolds.     

Dbf4-Cdc7 Phosphorylation of Mcm2 Is Required for Cell Growth

The Dbf4-Cdc7 kinase (DDK) is required for the activation of the origins of replication, and DDK phosphorylates Mcm2 in vitro. We find that budding yeast Cdc7 alone exists in solution as a weakly active multimer. Dbf4 forms a likely heterodimer with Cdc7, and this species phosphorylates Mcm2 with substantially higher specific activity. Dbf4 alone binds tightly to Mcm2, whereas Cdc7 alone binds weakly to Mcm2, suggesting that Dbf4 recruits Cdc7 to phosphorylate Mcm2. DDK phosphorylates two serine residues of Mcm2 near the N terminus of the protein, Ser-164 and Ser-170. Expression of mcm2-S170A is lethal to yeast cells that lack endogenous MCM2 (mcm2Δ); however, this lethality is rescued in cells harboring the DDK bypass mutant mcm5-bob1. We conclude that DDK phosphorylation of Mcm2 is required for cell growth.The Cdc7 protein kinase is required throughout the yeast S phase to activate origins (1, 2). The S phase cyclin-dependent kinase also activates yeast origins of replication (3–5). It has been proposed that Dbf4 activates Cdc7 kinase in S phase, and that Dbf4 interaction with Cdc7 is essential for Cdc7 kinase activity (6). However, it is not known how Dbf4-Cdc7 (DDK)² acts during S phase to trigger the initiation of DNA replication. DDK has homologs in other eukaryotic species, and the role of Cdc7 in activation of replication origins during S phase may be conserved (7–10).The Mcm2-7 complex functions with Cdc45 and GINS to unwind DNA at a replication fork (11–15). A mutation of MCM5 (mcm5-bob1) bypasses the cellular requirements for DBF4 and CDC7 (16), suggesting a critical physiologic interaction between Dbf4-Cdc7 and Mcm proteins. DDK phosphorylates Mcm2 in vitro with proteins purified from budding yeast (17, 18) or human cells (19). Furthermore, there are mutants of MCM2 that show synthetic lethality with DBF4 mutants (6, 17), suggesting a biologically relevant interaction between DBF4 and MCM2. Nevertheless, the physiologic role of DDK phosphorylation of Mcm2 is a matter of dispute. In human cells, replacement of MCM2 DDK-phosphoacceptor residues with alanines inhibits DNA replication, suggesting that Dbf4-Cdc7 phosphorylation of Mcm2 in humans is important for DNA replication (20). In contrast, mutation of putative DDK phosphorylation sites at the N terminus of Schizosaccharomyces pombe Mcm2 results in viable cells, suggesting that phosphorylation of S. pombe Mcm2 by DDK is not critical for cell growth (10).In budding yeast, Cdc7 is present at high levels in G₁ and S phase, whereas Dbf4 levels peak in S phase (18, 21, 22). Furthermore, budding yeast DDK binds to chromatin during S phase (6), and it has been shown that Dbf4 is required for Cdc7 binding to chromatin in budding yeast (23, 24), fission yeast (25), and Xenopus (9). Human and fission yeast Cdc7 are inert on their own (7, 8), but Dbf4-Cdc7 is active in phosphorylating Mcm proteins in budding yeast (6, 26), fission yeast (7), and human (8, 10). Based on these data, it has been proposed that Dbf4 activates Cdc7 kinase in S phase and that Dbf4 interaction with Cdc7 is essential for Cdc7 kinase activity (6, 9, 18, 21–24). However, a mechanistic analysis of how Dbf4 activates Cdc7 has not yet been accomplished. For example, the multimeric state of the active Dbf4-Cdc7 complex is currently disputed. A heterodimer of fission yeast Cdc7 (Hsk1) in complex with fission yeast Dbf4 (Dfp1) can phosphorylate Mcm2 (7). However, in budding yeast, oligomers of Cdc7 exist in the cell (27), and Dbf4-Cdc7 exists as oligomers of 180 and 300 kDa (27).DDK phosphorylates the N termini of human Mcm2 (19, 20, 28), human Mcm4 (10), budding yeast Mcm4 (26), and fission yeast Mcm6 (10). Although the sequences of the Mcm N termini are poorly conserved, the DDK sites identified in each study have neighboring acidic residues. The residues of budding yeast Mcm2 that are phosphorylated by DDK have not yet been identified.In this study, we find that budding yeast Cdc7 is weakly active as a multimer in phosphorylating Mcm2. However, a low molecular weight form of Dbf4-Cdc7, likely a heterodimer, has a higher specific activity for phosphorylation of Mcm2. Dbf4 or DDK, but not Cdc7, binds tightly to Mcm2, suggesting that Dbf4 recruits Cdc7 to Mcm2. DDK phosphorylates two serine residues of Mcm2, Ser-164 and Ser-170, in an acidic region of the protein. Mutation of Ser-170 is lethal to yeast cells, but this phenotype is rescued by the DDK bypass mutant mcm5-bob1. We conclude that DDK phosphorylation of Ser-170 of Mcm2 is required for budding yeast growth.     

Sip1, a Novel RS Domain-Containing Protein Essential for Pre-mRNA Splicing

Previous studies have shown that protein-protein interactions among splicing factors may play an important role in pre-mRNA splicing. We report here identification and functional characterization of a new splicing factor, Sip1 (SC35-interacting protein 1). Sip1 was initially identified by virtue of its interaction with SC35, a splicing factor of the SR family. Sip1 interacts with not only several SR proteins but also with U1-70K and U2AF65, proteins associated with 5′ and 3′ splice sites, respectively. The predicted Sip1 sequence contains an arginine-serine-rich (RS) domain but does not have any known RNA-binding motifs, indicating that it is not a member of the SR family. Sip1 also contains a region with weak sequence similarity to the Drosophila splicing regulator suppressor of white apricot (SWAP). An essential role for Sip1 in pre-mRNA splicing was suggested by the observation that anti-Sip1 antibodies depleted splicing activity from HeLa nuclear extract. Purified recombinant Sip1 protein, but not other RS domain-containing proteins such as SC35, ASF/SF2, and U2AF65, restored the splicing activity of the Sip1-immunodepleted extract. Addition of U2AF65 protein further enhanced the splicing reconstitution by the Sip1 protein. Deficiency in the formation of both A and B splicing complexes in the Sip1-depleted nuclear extract indicates an important role of Sip1 in spliceosome assembly. Together, these results demonstrate that Sip1 is a novel RS domain-containing protein required for pre-mRNA splicing and that the functional role of Sip1 in splicing is distinct from those of known RS domain-containing splicing factors.Pre-mRNA splicing takes place in spliceosomes, the large RNA-protein complexes containing pre-mRNA, U1, U2, U4/6, and U5 small nuclear ribonucleoprotein particles (snRNPs), and a large number of accessory protein factors (for reviews, see references 21, 22, 37, 44, and 48). It is increasingly clear that the protein factors are important for pre-mRNA splicing and that studies of these factors are essential for further understanding of molecular mechanisms of pre-mRNA splicing.Most mammalian splicing factors have been identified by biochemical fractionation and purification (3, 15, 19, 31–36, 45, 69–71, 73), by using antibodies recognizing splicing factors (8, 9, 16, 17, 61, 66, 67, 74), and by sequence homology (25, 52, 74).Splicing factors containing arginine-serine-rich (RS) domains have emerged as important players in pre-mRNA splicing. These include members of the SR family, both subunits of U2 auxiliary factor (U2AF), and the U1 snRNP protein U1-70K (for reviews, see references 18, 41, and 59). Drosophila alternative splicing regulators transformer (Tra), transformer 2 (Tra2), and suppressor of white apricot (SWAP) also contain RS domains (20, 40, 42). RS domains in these proteins play important roles in pre-mRNA splicing (7, 71, 75), in nuclear localization of these splicing proteins (23, 40), and in protein-RNA interactions (56, 60, 64). Previous studies by us and others have demonstrated that one mechanism whereby SR proteins function in splicing is to mediate specific protein-protein interactions among spliceosomal components and between general splicing factors and alternative splicing regulators (1, 1a, 6, 10, 27, 63, 74, 77). Such protein-protein interactions may play critical roles in splice site recognition and association (for reviews, see references 4, 18, 37, 41, 47 and 59). Specific interactions among the splicing factors also suggest that it is possible to identify new splicing factors by their interactions with known splicing factors.Here we report identification of a new splicing factor, Sip1, by its interaction with the essential splicing factor SC35. The predicted Sip1 protein sequence contains an RS domain and a region with sequence similarity to the Drosophila splicing regulator, SWAP. We have expressed and purified recombinant Sip1 protein and raised polyclonal antibodies against the recombinant Sip1 protein. The anti-Sip1 antibodies specifically recognize a protein migrating at a molecular mass of approximately 210 kDa in HeLa nuclear extract. The anti-Sip1 antibodies sufficiently deplete Sip1 protein from the nuclear extract, and the Sip1-depleted extract is inactive in pre-mRNA splicing. Addition of recombinant Sip1 protein can partially restore splicing activity to the Sip1-depleted nuclear extract, indicating an essential role of Sip1 in pre-mRNA splicing. Other RS domain-containing proteins, including SC35, ASF/SF2, and U2AF65, cannot substitute for Sip1 in reconstituting splicing activity of the Sip1-depleted nuclear extract. However, addition of U2AF65 further increases splicing activity of Sip1-reconstituted nuclear extract, suggesting that there may be a functional interaction between Sip1 and U2AF65 in nuclear extract.     

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]