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]     

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]     

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]     

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]     

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]     

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.     

In Vitro and In Vivo Biology of Recombinant Adenovirus Vectors with E1, E1/E2A,or E1/E4 Deleted

Isogenic, E3-deleted adenovirus vectors defective in E1, E1 and E2A, or E1 and E4 were generated in complementation cell lines expressing E1, E1 and E2A, or E1 and E4 and characterized in vitro and in vivo. In the absence of complementation, deletion of both E1 and E2A completely abolished expression of early and late viral genes, while deletion of E1 and E4 impaired expression of viral genes, although at a lower level than the E1/E2A deletion. The in vivo persistence of these three types of vectors was monitored in selected strains of mice with viral genomes devoid of transgenes to exclude any interference by immunogenic transgene-encoded products. Our studies showed no significant differences among the vectors in the short-term maintenance and long-term (4-month) persistence of viral DNA in liver and lung cells of immunocompetent and immunodeficient mice. Furthermore, all vectors induced similar antibody responses and comparable levels of adenovirus-specific cytotoxic T lymphocytes. These results suggest that in the absence of transgenes, the progressive deletion of the adenovirus genome does not extend the in vivo persistence of the transduced cells and does not reduce the antivirus immune response. In addition, our data confirm that, in the absence of transgene expression, mouse cellular immunity to viral antigens plays a minor role in the progressive elimination of the virus genome.Replication-deficient human adenoviruses (Ad) have been widely investigated as ex vivo and in vivo gene delivery systems for human gene therapy. The ability of these vectors to mediate the efficient expression of candidate therapeutic or vaccine genes in a variety of cell types, including postmitotic cells, is considered an advantage over other gene transfer vectors (3, 28, 49). However, the successful application of currently available E1-defective Ad vectors in human gene therapy has been hampered by the fact that transgene expression is only transient in vivo (2, 15, 16, 33, 36, 46). This short-lived in vivo expression of the transgene has been explained, at least in part, by the induction in vivo of cytotoxic immune responses to cells infected with the Ad vector. Studies with rodent systems have suggested that cytotoxic T lymphocytes (CTLs) directed against virus antigens synthesized de novo in the transduced tissues play a major role in eliminating cells containing the E1-deleted viral genome (56–58, 61). Consistent with the concept of cellular antiviral immunity, expression of transgenes is significantly extended in experimental rodent systems that are deficient in various components of the cellular immune system or that have been rendered immunocompromised by administration of pharmacological agents (2, 33, 37, 48, 60, 64).Based on the assumption that further reduction of viral antigen expression may lower the immune response and thus extend persistence of transgene expression, previous studies have investigated the consequences of deleting both E1 and an additional viral regulatory region, such as E2A or E4. The E2A region encodes a DNA binding protein (DBP) with specific affinity for single-stranded Ad DNA. The DNA binding function is essential for the initiation and elongation of viral DNA synthesis during the early phase of Ad infection. During the late phase of infection, DBP plays a central role in the activation of the major late promoter (MLP) (for a recent review, see reference 44). The E4 region, located at the right end of the viral genome, encodes several regulatory proteins with pleiotropic functions which are involved in the accumulation, splicing, and transport of early and late viral mRNAs, in DNA replication, and in virus particle assembly (reviewed in reference 44). The simultaneous deletion of E1 and E2A or of E1 and E4 should therefore further reduce the replication of the virus genome and the expression of early and late viral genes. Such multidefective vectors have been generated and tested in vitro and in vivo (9, 12, 17, 19–21, 23, 24, 26, 34, 40, 52, 53, 59, 62, 63). Recombinant vectors with E1 deleted and carrying an E2A temperature-sensitive mutation (E2Ats) have been shown in vitro to express much smaller amounts of virus proteins, leading to extended transgene expression in cotton rats and mice (19, 20, 24, 59). To eliminate the risks of reversion of the E2Ats point mutation to a wild-type phenotype, improved vectors with both E1 and E2A deleted were subsequently generated in complementation cell lines coexpressing E1 and E2A genes (26, 40, 63). In vitro analysis of human cells infected by these viruses demonstrated that the double deletion completely abolished viral DNA replication and late protein synthesis (26). Similarly, E1/E4-deleted vectors have been generated in various in vitro complementation systems and tested in vitro and in vivo (9, 17, 23, 45, 52, 53, 62). These studies showed that deletion of both E1 and E4 did indeed reduce significantly the expression of early and late virus proteins (17, 23), leading to a decreased anti-Ad host immune response (23), reduced hepatotoxicity (17, 23, 52), and improved in vivo persistence of the transduced liver cells (17, 23, 52).Interpretation of these results is difficult, however, since all tested E1- and E1/E4-deleted vectors encoded the bacterial β-galactosidase (βgal) marker, whose strong immunogenicity is known to influence the in vivo persistence of Ad-transduced cells (32, 37). Moreover, the results described above are not consistent with the conclusions from other studies showing, in various immunocompetent mouse models, that cellular immunity to Ad antigens has no detectable impact on the persistence of the transduced cells (37, 40, 50, 51). Furthermore, in contrast to results of earlier studies (19, 20, 59), Fang et al. (21) demonstrated that injection of E1-deleted/E2Ats vectors into immunocompetent mice and hemophilia B dogs did not lead to an improvement of the persistence of transgene expression compared to that with isogenic E1-deleted vectors. Similarly, Morral et al. (40) did not observe any difference in persistence of transgene expression in mice injected with either vectors deleted in E1 only or vectors deleted in both E1 and E2A. Finally, the demonstration that some E4-encoded products can modulate transgene expression (1, 17, 36a) makes the evaluation of E1- and E1/E4-deleted vectors even more complex when persistence of transgene expression is used for direct comparison of the in vivo persistence of cells transduced by the two types of vectors.The precise influence of the host immune response to viral antigens on the in vivo persistence of the transduced cells, and hence the impact of further deletions in the virus genome, therefore still remains unclear. To investigate these questions, we generated a set of isogenic vectors with single deletions (AdE1°) and double deletions (AdE1°E2A° and AdE1°E4°) and their corresponding complementation cell lines and compared the biologies and immunogenicities of these vectors in vitro and in vivo. To eliminate any possible influence of transgene-encoded products on the interpretation of the in vivo results, we used E1-, E1/E2A-, and E1/E4-deleted vectors with no transgenes.     

Phosphorylation Dependence of Hsp27 Multimeric Size and Molecular Chaperone Function

The molecular chaperone Hsp27 exists as a distribution of large oligomers that are disassembled by phosphorylation at Ser-15, -78, and -82. It is controversial whether the unphosphorylated Hsp27 or the widely used triple Ser-to-Asp phospho-mimic mutant is the more active molecular chaperone in vitro. This question was investigated here by correlating chaperone activity, as measured by the aggregation of reduced insulin or α-lactalbumin, with Hsp27 self-association as monitored by analytical ultracentrifugation. Furthermore, because the phospho-mimic is generally assumed to reproduce the phosphorylated molecule, the size and chaperone activity of phosphorylated Hsp27 were compared with that of the phospho-mimic. Hsp27 was triply phosphorylated by MAPKAP-2 kinase, and phosphorylation was tracked by urea-PAGE. An increasing degree of suppression of insulin or α-lactalbumin aggregation correlated with a decreasing Hsp27 self-association, which was the least for phosphorylated Hsp27 followed by the mimic followed by the unphosphorylated protein. It was also found that Hsp27 added to pre-aggregated insulin did not reverse aggregation but did inhibit these aggregates from assembling into even larger aggregates. This chaperone activity appears to be independent of Hsp27 phosphorylation. In conclusion, the most active chaperone of insulin and α-lactalbumin was the Hsp27 (elongated) dimer, the smallest Hsp27 subunit observed under physiological conditions. Next, the Hsp27 phospho-mimic is only a partial mimic of phosphorylated Hsp27, both in self-association and in chaperone function. Finally, the efficient inhibition of insulin aggregation by Hsp27 dimer led to the proposal of two models for this chaperone activity.Oligomeric heat shock protein 27 (Hsp27)² is a ubiquitous mammalian protein with a variety of functions in health and disease (1–8). These functions include ATP-independent chaperone activity in response to environmental stress, e.g. heat shock and oxidative stress, control of apoptosis, and regulation of actin cytoskeleton dynamics. Hsp27 is a member of the α-crystallin small heat shock protein family of which αB-crystallin is the archetype. These proteins are characterized by an α-crystallin domain of 80–90 residues consisting of roughly eight β-strands that form an intermolecular β-sheet interaction interface within a dimer, the basic building subunit of the oligomer (2, 4, 9–11).Hsp27 is in equilibrium between high molecular weight oligomers and much lower molecular weight multimers. It has been reported that unphosphorylated Hsp27 includes predominantly a distribution of high molecular species ranging in size from 12-mer to 35-mer (12–19). Phosphorylation of Hsp27 at serines 15, 78, and 82 by the p38-activated MAPKAP-2 kinase (20–22) or the use of the triple Ser-to-Asp phospho-mimic results in a major shift in the equilibrium toward much smaller multimers (23) and in an alteration of its function (1, 3, 6, 7, 24, 25). The size distribution of the smaller species has been reported to be between monomer and tetramer (12–16, 18, 19).Small heat shock proteins, including Hsp27, behave as ATP-independent molecular chaperones during cellular heat shock. They bind partially unfolded proteins and prevent their aggregation until the proteins can be refolded by larger ATP-dependent chaperones or are digested (7, 8, 26). This function includes the up-regulation and/or phosphorylation of Hsp27.It is not entirely clear what the role of Hsp27 size and phosphorylation state plays in its heat shock function because there are conflicting results in the literature. Some in vitro studies concluded that the unphosphorylated oligomeric Hsp27 (or the murine isoform Hsp25) protects proteins against aggregation better than does the phosphorylation mimic (13, 19, 27), whereas others found no difference (16, 28, 29), and still other studies found that the mimic protects better than does the unphosphorylated wild type (27, 30, 31). In-cell studies found that phosphorylation of Hsp27 was essential for thermo-protection of actin filaments (32), and the Hsp27 phosphorylation mimic decreased inclusion body formation better than did unphosphorylated Hsp27 (33). This study was undertaken to investigate the molecular chaperone function of Hsp27 by correlating chaperone activity with Hsp27 size and by comparing fully phosphorylated Hsp27 with its phospho-mimic.     

Inference of a Probabilistic Boolean Network from a Single Observed Temporal Sequence

The inference of gene regulatory networks is a key issue for genomic signal processing. This paper addresses the inference of probabilistic Boolean networks (PBNs) from observed temporal sequences of network states. Since a PBN is composed of a finite number of Boolean networks, a basic observation is that the characteristics of a single Boolean network without perturbation may be determined by its pairwise transitions. Because the network function is fixed and there are no perturbations, a given state will always be followed by a unique state at the succeeding time point. Thus, a transition counting matrix compiled over a data sequence will be sparse and contain only one entry per line. If the network also has perturbations, with small perturbation probability, then the transition counting matrix would have some insignificant nonzero entries replacing some (or all) of the zeros. If a data sequence is sufficiently long to adequately populate the matrix, then determination of the functions and inputs underlying the model is straightforward. The difficulty comes when the transition counting matrix consists of data derived from more than one Boolean network. We address the PBN inference procedure in several steps: (1) separate the data sequence into "pure" subsequences corresponding to constituent Boolean networks; (2) given a subsequence, infer a Boolean network; and (3) infer the probabilities of perturbation, the probability of there being a switch between constituent Boolean networks, and the selection probabilities governing which network is to be selected given a switch. Capturing the full dynamic behavior of probabilistic Boolean networks, be they binary or multivalued, will require the use of temporal data, and a great deal of it. This should not be surprising given the complexity of the model and the number of parameters, both transitional and static, that must be estimated. In addition to providing an inference algorithm, this paper demonstrates that the data requirement is much smaller if one does not wish to infer the switching, perturbation, and selection probabilities, and that constituent-network connectivity can be discovered with decent accuracy for relatively small time-course sequences.[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]