Acetylome Analysis Reveals Diverse Functions of Lysine Acetylation in Mycobacterium tuberculosis

The lysine acetylation of proteins is a reversible post-translational modification that plays a critical regulatory role in both eukaryotes and prokaryotes. Mycobacterium tuberculosis is a facultative intracellular pathogen and the causative agent of tuberculosis. Increasing evidence shows that lysine acetylation may play an important role in the pathogenesis of M. tuberculosis. However, only a few acetylated proteins of M. tuberculosis are known, presenting a major obstacle to understanding the functional roles of reversible lysine acetylation in this pathogen. We performed a global acetylome analysis of M. tuberculosis H37Ra by combining protein/peptide prefractionation, antibody enrichment, and LC-MS/MS. In total, we identified 226 acetylation sites in 137 proteins of M. tuberculosis H37Ra. The identified acetylated proteins were functionally categorized into an interaction map and shown to be involved in various biological processes. Consistent with previous reports, a large proportion of the acetylation sites were present on proteins involved in glycolysis/gluconeogenesis, the citrate cycle, and fatty acid metabolism. A NAD⁺-dependent deacetylase (MRA_1161) deletion mutant of M. tuberculosis H37Ra was constructed and its characterization showed a different colony morphology, reduced biofilm formation, and increased tolerance of heat stress. Interestingly, lysine acetylation was found, for the first time, to block the immunogenicity of a peptide derived from a known immunogen, HspX, suggesting that lysine acetylation plays a regulatory role in immunogenicity. Our data provide the first global survey of lysine acetylation in M. tuberculosis. The dataset should be an important resource for the functional analysis of lysine acetylation in M. tuberculosis and facilitate the clarification of the entire metabolic networks of this life-threatening pathogen.Mycobacterium tuberculosis was responsible for 1.3 million deaths and 8.6 million new cases of tuberculosis (TB)¹ worldwide in 2012 (1). This global public health crisis remains a serious problem, with the emergence of drug-resistant M. tuberculosis, especially multidrug-resistant and extensively drug-resistant M. tuberculosis, and also the emergence of coinfections of TB and human immunodeficiency virus (2, 3). To counter the increasing threat of TB, it is critical to understand fundamental aspects of TB-related biology. Such studies will not only provide new drug targets for the design of novel therapeutic agents, but also facilitate the development of novel diagnostic tools and new vaccines.Acetylation is one of the important protein modifications and occurs both co- and post-translationally on the α-amino group at the N terminus of the protein, so-called “N-terminal acetylation,” or on the ε-amino group on the side chain of lysine (4). Lysine acetylation is one of the most common post-translational modifications to proteins in both eukaryotes and prokaryotes. As a dynamic and reversible process, protein acetylation plays important roles in many cellular physiological processes, including cell-cycle regulation and apoptosis, cell morphology (5), metabolic pathways (6–8), protein interactions (9), and enzymatic activity (8, 10). In recent years, great advances have been made in proteomic studies, and a large number of lysine-acetylated proteins have been identified in many eukaryotes, including human (5, 11, 12), rat (13), mouse (11), Drosophila (14), Arabidopsis (15, 16), Saccharomyces cerevisiae (17), and protozoans (18, 19). The global analysis of lysine acetylation has also been reported in bacteria, including Escherichia coli (20–22), Erwinia amylovora (23), Bacillus subtilis (24), and Salmonella enterica (6). These acetylome studies have generated large datasets of bacterial proteins acetylated on lysine residues and have demonstrated the diverse cellular functions of lysine acetylation in bacteria.Increasing evidence shows that protein acetylation occurs and plays an important regulatory role in mycobacteria (8, 25–31). For example, Lange et al. reported the N-terminal acetylation of early secreted antigenic target 6 (ESAT-6) protein (31). Rv1151c is reported to be an NAD⁺-dependent protein deacetylase in M. tuberculosis that deacetylates and thus regulates the activity of acetyl-CoA synthase (25, 32). Two cyclic adenosine monophosphate (cAMP)-binding proteins in M. smegmatis and M. tuberculosis (MSMEG_5458 and Rv0998, respectively) show similarity to the GNAT family of acetyltransferases and could acetylate a universal stress protein (USP, MSMEG_4207) (30). Subsequent structural studies revealed the fine mechanisms of how cAMP regulates the protein lysine acetyltransferase in mycobacteria (27, 28). Very recently, reversible lysine acetylation was shown to regulate the activity of several fatty acyl-CoA synthetases in M. tuberculosis (8, 26), and also to regulate acetate and propionate metabolism in M. smegmatis (8, 26). However, to the best of our knowledge, only a few acetylated proteins in M. tuberculosis have been identified, presenting a major obstacle to further understanding the regulatory roles of reversible lysine acetylation in this life-threatening pathogen.To fill this gap in our knowledge, we undertook a systematic study of the functional roles of lysine acetylation in M. tuberculosis. We performed an acetylomic analysis of M. tuberculosis H37Ra using high-accuracy MS combined with the identification of 226 unique lysine acetylation sites on 137 proteins. This set of M. tuberculosis proteins acetylated on lysine residues supports the emerging view that lysine acetylation is a general and fundamental regulatory process, and is not restricted to eukaryotes. It also opens the way for its detailed functional and evolutionary analysis of lysine acetylation in M. tuberculosis. The identified acetylated proteins that are involved in several important biological processes were functionally categorized into an interaction map. This is the first time that an interaction network of acetylated proteins in M. tuberculosis has been constructed, and should allow us to better understand the significance of acetylation in key cellular mechanisms in M. tuberculosis. To further explore the effects of lysine acetylation on the physiology of M. tuberculosis H37Ra, MRA_1161, the gene encoding the only known protein deacetylase in this bacterium, was deleted. The roles of MRA_1161 in the colony morphology, carbon source utilization, heat stress tolerance, and biofilm formation of M. tuberculosis were analyzed. The effect of lysine acetylation on the immunogenicity of a known immunogen, HspX, was also tested.     

Immunoproteomic Identification of Human T Cell Antigens of Mycobacterium tuberculosis That Differentiate Healthy Contacts from Tuberculosis Patients

Identification of Mycobacterium tuberculosis antigens inducing cellular immune responses is required to improve the diagnosis of and vaccine development against tuberculosis. To identify the antigens of M. tuberculosis that differentiated between tuberculosis (TB) patients and healthy contacts based on T cell reactivity, the culture filtrate of in vitro grown M. tuberculosis was fractionated by two-dimensional liquid phase electrophoresis and tested for the ability to stimulate T cells in a whole blood assay. This approach separated the culture filtrate into 350 fractions with sufficient protein quantity (at least 200 μg of protein) for mass spectrometry and immunological analyses. High levels of interferon-γ (IFN-γ) secretion were induced by 105 fractions in healthy contacts compared with TB patients (p < 0.05). Most interesting was the identification of 10 fractions that specifically induced strong IFN-γ production in the healthy contact population but not in TB patients. Other immunological measurements showed 42 fractions that induced significant lymphocyte proliferative responses in the healthy contact group compared with the TB patients. The tumor necrosis factor-α response for most of the fractions did not significantly differ in the tested groups, and the interleukin-4 response was below the detectable range for all fractions and both study groups. Proteomic characterization of the 105 fractions that induced a significant IFN-γ response in the healthy contacts compared with the TB patients led to the identification of 59 proteins of which 24 represented potentially novel T cell antigens. Likewise, the protein identification in the 10 healthy “contact-specific fractions” revealed 16 proteins that are key candidates as vaccine or diagnostic targets.Tuberculosis (TB)1 is a major health problem throughout the world. A recent World Health Organization report shows that TB has been increasing at a rate of 1% per year, and an estimated 9.2 million new cases arise each year (1). Although TB is preventable, there has been an increase in its incidence in recent years. Re-emergence of TB is mainly due to its association with human immunodeficiency virus infection (2) and also due to the occurrence of multidrug-resistant strains of the causative agent, Mycobacterium tuberculosis (3).Vaccination of general population is cost effective and represents one of the best biological measures for disease control. The current vaccine against tuberculosis, Bacille Calmette-Guérin (BCG), has been administered to more people than any other vaccine. The side effects of BCG are tolerable, and it prevents miliary and meningeal tuberculosis in young children. In striking contrast, it affords limited and highly variable protection (0–80%) against pulmonary TB (4). Thus, BCG does not seem to be a satisfactory vaccine (5, 6) and necessitates exploration of newer strategies to improve BCG or to develop a more effective vaccine.One of the potential strategies for the development of an improved TB vaccine involves the use of the proteins secreted by M. tuberculosis during growth. There is evidence that proteins actively secreted by M. tuberculosis during growth induce cell-mediated immune responses by causing expansion of specific interferon-γ (IFN-γ)-producing T lymphocytes that are capable of recognizing and exerting antimicrobial effects against infected macrophages (7). The importance of IFN-γ pathways in host defense against M. tuberculosis was clarified by experimental studies on IFN-γ knock-out mice as well as the identification and characterization of humans with mutations in IFN-γ receptor (8, 9).Several studies have been carried out to define the secreted proteome of M. tuberculosis. The earliest study aimed at the identification of mycobacterial culture filtrate proteins, using chromatography and N-terminal sequencing to identify eight culture filtrate proteins (10). Later, many studies used two-dimensional (2D) PAGE combined with sensitive mass spectrometric methods for identification of proteins. The above mentioned approaches have identified nearly 300 culture filtrate proteins (11–13).Identification of T cell antigens in a complex mixture was first done by a T cell Western blot method (14). Later, two-dimensional separation methods were used that involved protein separation by either IEF (15) or chromatography (16) in the first dimension and preparative SDS-PAGE followed by whole gel elution (17) in the second dimension. Mouse T cell antigens of M. tuberculosis were identified using this method (15). Mycobacterial antigens that induce an immune response in healthy household contacts and treated TB patients were also mapped using this approach (16).In the present study, 2D liquid phase electrophoresis (LPE) along with an in vitro IFN-γ assay and LC-MS/MS were used to identify potential human T cell antigens. Systematic screening of the M. tuberculosis culture filtrate (CF) proteome and comparative evaluation of cellular immune responses between TB patients and healthy contacts led to the identification of 59 proteins in the most immunogenic 2D LPE fractions. Twenty-four potentially novel T cell antigens were identified, and 16 proteins were identified in 10 2D LPE fractions that differentiated healthy contacts from TB patients based on IFN-γ responses.     

Succinylome Analysis Reveals the Involvement of Lysine Succinylation in Metabolism in Pathogenic Mycobacterium tuberculosis

Mycobacterium tuberculosis (Mtb), the causative agent of human tuberculosis, remains one of the most prevalent human pathogens and a major cause of mortality worldwide. Metabolic network is a central mediator and defining feature of the pathogenicity of Mtb. Increasing evidence suggests that lysine succinylation dynamically regulates enzymes in carbon metabolism in both bacteria and human cells; however, its extent and function in Mtb remain unexplored. Here, we performed a global succinylome analysis of the virulent Mtb strain H37Rv by using high accuracy nano-LC-MS/MS in combination with the enrichment of succinylated peptides from digested cell lysates and subsequent peptide identification. In total, 1545 lysine succinylation sites on 626 proteins were identified in this pathogen. The identified succinylated proteins are involved in various biological processes and a large proportion of the succinylation sites are present on proteins in the central metabolism pathway. Site-specific mutations showed that succinylation is a negative regulatory modification on the enzymatic activity of acetyl-CoA synthetase. Molecular dynamics simulations demonstrated that succinylation affects the conformational stability of acetyl-CoA synthetase, which is critical for its enzymatic activity. Further functional studies showed that CobB, a sirtuin-like deacetylase in Mtb, functions as a desuccinylase of acetyl-CoA synthetase in in vitro assays. Together, our findings reveal widespread roles for lysine succinylation in regulating metabolism and diverse processes in Mtb. Our data provide a rich resource for functional analyses of lysine succinylation and facilitate the dissection of metabolic networks in this life-threatening pathogen.Post-translational modifications (PTMs)¹ are complex and fundamental mechanisms modulating diverse protein properties and functions, and have been associated with almost all known cellular pathways and disease processes (1, 2). Among the hundreds of different PTMs, acylations at lysine residues, such as acetylation (3–6), malonylation (7, 8), crotonylation (9, 10), propionylation (11–13), butyrylation (11, 13), and succinylation (7, 14–16) are crucial for functional regulations of many prokaryotic and eukaryotic proteins. Because these lysine PTMs depend on the acyl-CoA metabolic intermediates, such as acetyl-CoA (Ac-CoA), succinyl-CoA, and malonyl-CoA, lysine acylation could provide a mechanism to respond to changes in the energy status of the cell and regulate energy metabolism and the key metabolic pathways in diverse organisms (17, 18).Among these lysine PTMs, lysine succinylation is a highly dynamic and regulated PTM defined as transfer of a succinyl group (-CO-CH₂-CH₂-CO-) to a lysine residue of a protein molecule (8). It was recently identified and comprehensively validated in both bacterial and mammalian cells (8, 14, 16). It was also identified in core histones, suggesting that lysine succinylation may regulate the functions of histones and affect chromatin structure and gene expression (7). Accumulating evidence suggests that lysine succinylation is a widespread and important PTM in both eukaryotes and prokaryotes and regulates diverse cellular processes (16). The system-wide studies involving lysine-succinylated peptide immunoprecipitation and liquid chromatography-mass spectrometry (LC-MS/MS) have been employed to analyze the bacteria (E. coli) (14, 16), yeast (S. cerevisiae), human (HeLa) cells, and mouse embryonic fibroblasts and liver cells (16, 19). These succinylome studies have generated large data sets of lysine-succinylated proteins in both eukaryotes and prokaryotes and demonstrated the diverse cellular functions of this PTM. Notably, lysine succinylation is widespread among diverse mitochondrial metabolic enzymes that are involved in fatty acid metabolism, amino acid degradation, and the tricarboxylic acid cycle (19, 20). Thus, lysine succinylation is reported as a functional PTM with the potential to impact mitochondrial metabolism and coordinate different metabolic pathways in human cells and bacteria (14, 19–22).Mycobacterium tuberculosis (Mtb), the causative agent of tuberculosis (TB), is a major cause of mortality worldwide and claims more human lives annually than any other bacterial pathogen (23). About one third of the world''s population is infected with Mtb, which leads to nearly 1.3 million deaths and 8.6 million new cases of TB in 2012 worldwide (24). Mtb remains a major threat to global health, especially in the developing countries. Emergence of multidrug resistant (MDR) and extensively drug-resistant (XDR) Mtb, and also the emergence of co-infection between TB and HIV have further worsened the situation (25–27). Among bacterial pathogens, Mtb has a distinctive life cycle spanning different environments and developmental stages (28). Especially, Mtb can exist in dormant or active states in the host, leading to asymptomatic latent TB infection or active TB disease (29). To achieve these different physiologic states, Mtb developed a mechanism to sense diverse signals from the host and to coordinately regulate multiple cellular processes and pathways (30, 31). Mtb has evolved its metabolic network to both maintain and propagate its survival as a species within humans (32–35). It is well accepted that metabolic network is a central mediator and defining feature of the pathogenicity of Mtb (23, 36–38). Knowledge of the regulation of metabolic pathways used by Mtb during infection is therefore important for understanding its pathogenicity, and can also guide the development of novel drug therapies (39). On the other hand, increasing evidence suggests that lysine succinylation dynamically regulates enzymes in carbon metabolism in both bacteria and human cells (14, 19–22). It is tempting to speculate that lysine succinylation may play an important regulatory role in metabolic processes in Mtb. However, to the best of our knowledge, no succinylated protein in Mtb has been identified, presenting a major obstacle to understand the regulatory roles of lysine succinylation in this life-threatening pathogen.In order to fill this gap in our knowledge, we have initiated a systematic study of the identities and functional roles of the succinylated protein in Mtb. Because Mtb H37Rv is the first sequenced Mtb strain (40) and has been extensively used for studies in dissecting the roles of individual genes in pathogenesis (41), it was selected as a test case. We analyzed the succinylome of Mtb H37Rv by using high accuracy nano-LC-MS/MS in combination with the enrichment of succinylated peptides from digested cell lysates and subsequent peptide identification. In total, 1545 lysine succinylation sites on 626 proteins were identified in this pathogen. The identified succinylated proteins are involved in various biological processes and render particular enrichment to metabolic process. A large proportion of the succinylation sites are present on proteins in the central metabolism pathway. We further dissected the regulatory role of succinylation on acetyl-CoA synthetase (Acs) via site-specific mutagenesis analysis and molecular dynamics (MD) simulations showed that reversible lysine succinylation could inhibit the activity of Acs. Further functional studies showed that CobB, a sirtuin-like deacetylase in Mtb, functions as a deacetylase and as a desuccinylase of Acs in in vitro assays. Together, our findings provide significant insights into the range of functions regulated by lysine succinylation in Mtb.     

Characterization of Mycobacterium leprae RecA Intein, a LAGLIDADG Homing Endonuclease, Reveals a Unique Mode of DNA Binding, Helical Distortion, and Cleavage Compared with a Canonical LAGLIDADG Homing Endonuclease

Mycobacterium leprae, which has undergone reductive evolution leaving behind a minimal set of essential genes, has retained intervening sequences in four of its genes implicating a vital role for them in the survival of the leprosy bacillus. A single in-frame intervening sequence has been found embedded within its recA gene. Comparison of the M. leprae recA intervening sequence with the known intervening sequences indicated that it has the consensus amino acid sequence necessary for being a LAGLIDADG-type homing endonuclease. In light of massive gene decay and function loss in the leprosy bacillus, we sought to investigate whether its recA intervening sequence encodes a catalytically active homing endonuclease. Here we show that the purified M. leprae RecA intein (PI-MleI) binds to cognate DNA and displays endonuclease activity in the presence of alternative divalent cations, Mg²⁺ or Mn²⁺. A combination of approaches, including four complementary footprinting assays such as DNase I, copper-phenanthroline, methylation protection, and KMnO₄, enhancement of 2-aminopurine fluorescence, and mapping of the cleavage site revealed that PI-MleI binds to cognate DNA flanking its insertion site, induces helical distortion at the cleavage site, and generates two staggered double strand breaks. Taken together, these results implicate that PI-MleI possesses a modular structure with separate domains for DNA target recognition and cleavage, each with distinct sequence preferences. From a biological standpoint, it is tempting to speculate that our findings have implications for understanding the evolution of the LAGLIDADG family of homing endonucleases.Mycobacterium leprae, a Gram-positive rod-shaped bacillus, mostly found in warm tropical countries, is the bacterium that causes leprosy in humans (1). The lack of understanding of the basic biology of M. leprae is believed to be the key factor for the failure of leprosy research to advance. The genome sequence of M. leprae contains 3.27 Mb and has an average G + C content of 57.8%, values much lower than the corresponding values for Mycobacterium tuberculosis, which are ∼4.41 Mb and 65.6% G + C, respectively (2). There are some 1500 genes that are common to both M. leprae and M. tuberculosis. The comparative genome analysis suggests that both species of mycobacteria are derived from a common ancestor and, at one stage, had gene pools of similar size. The downsizing of the M. tuberculosis genome from ∼4.41 to 3.27 Mb of M. leprae would account for the loss of some 1200 protein-coding sequences (1, 3). There is evidence that many of the genes that were present in the genome of M. leprae have truly been lost (1, 3). Comparative genomics of M. leprae with that of M. tuberculosis indicate that the former has undergone substantial downsizing, losing more than 2000 genes, thus suggesting an extreme case of reductive evolution in a microbial pathogen (1). With the availability of the M. leprae genome sequence, using functional genomics approaches, it is possible to identify the gene products, elucidate the mechanism of their action, and identify novel drug targets for rational design of new therapeutic regimens and drugs to treat leprosy.Eubacterial RecA proteins catalyze a set of biochemical reactions that are essential for homologous recombination, DNA repair, restoration of stalled replication forks, and SOS response (4–7). RecA protein and the process of homologous recombination, which is the main mechanism of genetic exchange, are evolutionarily conserved among a range of organisms (4, 7). Perhaps the most striking development in the field of RecA protein biology was the discovery of an in-frame insertion of an intein-coding sequence in the recA genes of M. tuberculosis and M. leprae (8, 9). In these organisms, RecA is synthesized as a large precursor, which undergoes protein splicing to excise the intein, and the two flanking domains called exteins are ligated together to generate a functionally active RecA protein (9, 10). The milieu in which RecA precursor undergoes splicing differs substantially between M. tuberculosis and M. leprae. M. leprae RecA precursor (79 kDa) undergoes splicing only in mycobacterial species, whereas M. tuberculosis RecA precursor (85 kDa) is spliced efficiently in Escherichia coli as well (9–11). Intriguingly, M. tuberculosis and M. leprae RecA inteins differ greatly in their size, primary sequence, and location within the recA gene, thereby suggesting two independent origins during evolution (9). The occurrence of inteins in the obligate mycobacterial pathogens, M. tuberculosis, M. leprae, and Mycobacterium microti, suggested that RecA inteins might play a role in mycobacterial functions related to pathogenesis or virulence (9). Previously, we have shown that M. tuberculosis RecA intein (PI-MtuI),² which contains Walker A motif, displays dual target specificity in the presence of alternative cofactors in an ATP-dependent manner (12, 13).Since their discovery in Saccharomyces cerevisiae (14, 15), a large number of putative homing endonucleases have been found in a diverse range of proteins in all the three domains of life (16–19). The majority of inteins possess the protein splicing and homing endonuclease activities (18, 19). Homing endonucleases are a class of diverse rare-cutting enzymes that promote site-specific transposition of their encoding genetic elements by inflicting double-stranded DNA breaks via different cleavage mechanisms in alleles lacking these elements (18–23). In addition, these are characterized by their ability to bind long DNA target sites (14–40 bp), and their tolerance of minor sequence changes in their binding region. These have been divided into highly divergent subfamilies on the basis of conserved sequence and structural motifs as follows: LAGLIDADG, GIY-YIG, HNH, His-Cys box, and the more recently identified PD(D/E)XK families (18–24). LAGLIDADG homing enzymes, which include the largest family, contain one or two copies of the conserved dodecapeptide motif and utilize an extended protein-DNA interface covering up to 40 bp to acquire their necessary specificity (18–22). The LAGLIDADG sequence is a part of the conserved 10- or 12-residue sequence motif defining the family of LAGLIDADG-type homing endonucleases; therefore, it is designated as deca- or dodecapeptide motif (19).Comparison of the M. leprae recA intervening sequence with known intervening sequences indicated that it has the consensus amino acid sequence necessary for being a LAGLIDADG-type homing endonuclease (25, 26). In light of massive gene decay and function loss in the leprosy bacillus, and dissimilarities in size and primary structures among mycobacterial inteins, we sought to investigate whether M. leprae recA intervening sequence encodes a catalytically active homing endonuclease. In this study, we show that the purified M. leprae RecA intein (PI-MleI) binds to cognate DNA and displays endonuclease activity in the presence of alternative divalent cations Mg²⁺ or Mn²⁺. Furthermore, using a variety of approaches, we have mapped the positions of PI-MleI binding as well as cleavage in the cognate DNA, thus providing the most comprehensive analysis of PI-MleI. Taken together, these results suggest that PI-MleI possesses a modular structure with functionally separable domains for DNA target recognition and cleavage, each with distinct sequence preferences. These results provide insights into understanding the function and evolution of the family of LAGLIDADG homing endonucleases.     

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]     

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]