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]     

Proteome-wide Analysis of Lysine Acetylation Suggests its Broad Regulatory Scope in Saccharomyces cerevisiae

Post-translational modification of proteins by lysine acetylation plays important regulatory roles in living cells. The budding yeast Saccharomyces cerevisiae is a widely used unicellular eukaryotic model organism in biomedical research. S. cerevisiae contains several evolutionary conserved lysine acetyltransferases and deacetylases. However, only a few dozen acetylation sites in S. cerevisiae are known, presenting a major obstacle for further understanding the regulatory roles of acetylation in this organism. Here we use high resolution mass spectrometry to identify about 4000 lysine acetylation sites in S. cerevisiae. Acetylated proteins are implicated in the regulation of diverse cytoplasmic and nuclear processes including chromatin organization, mitochondrial metabolism, and protein synthesis. Bioinformatic analysis of yeast acetylation sites shows that acetylated lysines are significantly more conserved compared with nonacetylated lysines. A large fraction of the conserved acetylation sites are present on proteins involved in cellular metabolism, protein synthesis, and protein folding. Furthermore, quantification of the Rpd3-regulated acetylation sites identified several previously known, as well as new putative substrates of this deacetylase. Rpd3 deficiency increased acetylation of the SAGA (Spt-Ada-Gcn5-Acetyltransferase) complex subunit Sgf73 on K33. This acetylation site is located within a critical regulatory domain in Sgf73 that interacts with Ubp8 and is involved in the activation of the Ubp8-containing histone H2B deubiquitylase complex. Our data provides the first global survey of acetylation in budding yeast, and suggests a wide-ranging regulatory scope of this modification. The provided dataset may serve as an important resource for the functional analysis of lysine acetylation in eukaryotes.Lysine acetylation is a dynamic and reversible post-translational modification. Acetylation of lysines on their ε-amino group is catalyzed by lysine acetyltransferases (KATs¹, also known as histone acetyltrasferases (HATs)), and reversed by lysine deacetylases (KDACs, also known as histone deacetylases (HDACs)) (1). The enzymatic machinery involved in lysine acetylation is evolutionary conserved in all forms of life (2–4). The role of acetylation has been extensively studied in the regulation of gene expression via modification of histones (5). Acetylation also plays important roles in controlling cellular metabolism (6–10), protein folding (11), and sister chromatid cohesion (12). Furthermore, acetylation has been implicated in regulating the beneficial effects of calorie restriction (13), a low nutrient diet without starvation, and aging. Based on these findings, it is proposed that the functional roles of acetylation in these processes are evolutionary conserved from yeast to mammals.Advancements in mass spectrometry (MS)-based proteomics have greatly facilitated identification of thousands of post-translational modification (PTM) sites in eukaryotic cells (14–18). Proteome-wide mapping of PTM sites can provide important leads for analyzing the functional relevance of individual sites and a systems-wide view of the regulatory scope of post-translational modifications. Also, large-scale PTM datasets are an important resource for the in silico analysis of PTMs, which can broaden the understanding of modification site properties and their evolutionary trajectories.The budding yeast Saccharomyces cerevisiae is a commonly used unicellular eukaryotic model organism. Yeast has been used in many pioneering “-omics” studies, including sequencing of the first eukaryotic genome (19), systems-wide genetic interactions analysis (20, 21), MS-based comprehensive mapping of a eukaryotic proteome (22), and proteome-wide analysis of protein-protein interactions (23, 24). In addition, S. cerevisiae has been extensively used to study the molecular mechanisms of acetylation. Many lysine acetyltransferases and deacetylases were discovered in this organism (2, 25), and their orthologs were subsequently identified in higher eukaryotes. Furthermore, the functional roles of many well-studied acetylation sites on histones are conserved from yeast to mammals. Recent data from human and Drosophila cells show that acetylation is present on many highly conserved metabolic enzymes (26–28). However, only a few dozen yeast acetylation sites are annotated in the Uniprot database. Given the presence of a well-conserved and elaborate acetylation machinery in yeast, we reasoned that many more acetylation sites exist in this organism that remained to be identified.Here we used high resolution mass spectrometry-based proteomics to investigate the scope of acetylation in S. cerevisiae. We identified about 4000 unique acetylation sites in this important model organism. Bioinformatic analysis of yeast acetylation sites and comparison with previously identified human and Drosophila acetylation sites indicates that many acetylation sites are evolutionary conserved. Furthermore, quantitative analysis of the Rpd3-regulated acetylation sites identified several nuclear proteins that showed increased acetylation in rpd3 knockout cells. Our results provide a systems-wide view of acetylation in budding yeast, and a rich dataset for functional analysis of acetylation sites in this organism.     

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]     

Protein N-terminal Acetyltransferases Act as N-terminal Propionyltransferases In Vitro and In Vivo

N-terminal acetylation (Nt-acetylation) is a highly abundant protein modification in eukaryotes catalyzed by N-terminal acetyltransferases (NATs), which transfer an acetyl group from acetyl coenzyme A to the alpha amino group of a nascent polypeptide. Nt-acetylation has emerged as an important protein modifier, steering protein degradation, protein complex formation and protein localization. Very recently, it was reported that some human proteins could carry a propionyl group at their N-terminus. Here, we investigated the generality of N-terminal propionylation by analyzing its proteome-wide occurrence in yeast and we identified 10 unique in vivo Nt-propionylated N-termini. Furthermore, by performing differential N-terminome analysis of a control yeast strain (yNatA), a yeast NatA deletion strain (yNatAΔ) or a yeast NatA deletion strain expressing human NatA (hNatA), we were able to demonstrate that in vivo Nt-propionylation of several proteins, displaying a NatA type substrate specificity profile, depended on the presence of either yeast or human NatA. Furthermore, in vitro Nt-propionylation assays using synthetic peptides, propionyl coenzyme A, and either purified human NATs or immunoprecipitated human NatA, clearly demonstrated that NATs are Nt-propionyltransferases (NPTs) per se. We here demonstrate for the first time that Nt-propionylation can occur in yeast and thus is an evolutionarily conserved process, and that the NATs are multifunctional enzymes acting as NPTs in vivo and in vitro, in addition to their main role as NATs, and their potential function as lysine acetyltransferases (KATs) and noncatalytic regulators.Modifications greatly increases a cell''s proteome diversity confined by the natural amino acids. As more than 80% of human proteins, more than 70% of plant and fly proteins and more than 60% of yeast proteins are N-terminally acetylated (Nt-acetylated),¹ this modification represents one of the most common protein modifications in eukaryotes (1–5). Recent studies have pointed to distinct functional consequences of Nt-acetylation (6): creating degradation signals recognized by a ubiquitin ligase of a new branch of the N-end rule pathway (7), preventing translocation across the endoplasmic reticulum membrane (8), and mediating protein complex formation (9). Nt-acetylation further appears to be essential for life in higher eukaryotes; for instance, a mutation in the major human N-terminal acetyltransferase (NAT), hNatA, was recently shown to be the cause of Ogden syndrome by which male infants are underdeveloped and die at infancy (10). Unlike lysine acetylation, Nt-acetylation is considered an irreversible process, and further, to mainly occur on the ribosome during protein synthesis (11–15). In yeast and humans, three NAT complexes are responsible for the majority of Nt-acetylation; NatA, NatB and NatC, each of which has a defined substrate specificity (16). NatA acetylates Ser-, Ala-, Gly-, Thr-, Val- and Cys- N-termini generated on removal of the initiator methionine (iMet) (1, 17–19). NatB and NatC acetylate N-termini in which the iMet is followed by an acidic (20–23) or a hydrophobic residue respectively (24–26). Naa40p/NatD was shown to acetylate the Ser-starting N-termini of histones H2A and H4 (27, 28). NatE, composed of the catalytic Naa50p (Nat5p) has substrate specificity toward iMet succeeded by a hydrophobic amino acid (29, 30). As largely the same Nt-acetylation patterns are found in yeast and humans, it was believed that the NAT-machineries were conserved in general (31). However, the recently discovered higher eukaryotic specific NAT, Naa60p/NatF, was found to display a partially distinct substrate specificity in part explaining the higher degree of Nt-acetylation in higher versus lower eukaryotes (4).Human NatA is composed of two main subunits: the catalytic subunit hNaa10p and the auxiliary subunit, hNaa15p that is presumably responsible for anchoring the complex to the ribosome (14, 19). The chaperone-like HYPK protein is also stably associated with the NatA subunits and may be essential for efficient NatA activity (32). In addition, hNaa50p was shown to be physically associated with hNatA, however it is believed not to affect NatA activity (14, 33, 34). hNaa50p was also shown to exhibit N^ε-acetyltransferase (KAT) activity (29), however, the structure of hNaa50p with its peptide substrate bound strongly indicates that the peptide binding pocket is specifically suited to accommodate N-terminal peptides, as opposed to lysine residues (35). The human NatA subunits are associated with ribosomes, but interestingly, significant fractions are also nonribosomal (19, 30, 32). Of further notice, the catalytic subunits, hNaa10p and hNaa50p, were also found to partially act independently of the hNatA complex (30, 36).Recent studies have identified novel in vivo acyl modifications of proteins. Mass spectrometry data of affinity-enriched acetyllysine-containing peptides from HeLa cells showed the presence of propionylated and butyrylated lysines in histone H4 peptides (37). Similar analyses also showed the presence of propionylated lysines in p53, p300 and CREB-binding protein (38) besides the yeast histones H2B, H3 and H4 (39). Propionylated or butyrylated residues differ by only one or two extra methyl moieties as compared with their acetylated counterparts, thereby adding more hydrophobicity and bulkiness to the affected residue. To date, no distinct propionyl- or butyryltransferases responsible for these modifications have been identified. However, by using propionyl coenzyme A (Prop-CoA) or butyryl coenzyme A (But-CoA) as donors in the enzyme reaction, it was shown that some of the previously characterized lysine acetyltransferases (KATs) are able to respectively catalyze propionylation and butyrylation of lysine residues both in vitro (37, 40–42) and in vivo (38, 41). Similarly, it has been shown that lysine deacetylases also are capable of catalyzing depropionylation (40, 41, 43, 44) and debutyrylation (44) (see review (45)).Interestingly, mass spectrometry data also suggested that propionylated N-termini are present in human cell lines (46, 47). Until today, an N-terminal propionyl transferase (NPT) catalyzing N-terminal propionylation (Nt-propionylation) has to our knowledge not been identified.In this study, we hypothesized that NATs might have the ability to act as NPTs. In vitro experiments using purified hNaa10p, hNaa50p or immunoprecipitated human NatA complex indeed confirmed their intrinsic capacity to catalyze Nt-propionylation toward synthetic peptides. NatA was also found capable of Nt-butyrylation in vitro. By means of N-terminomics, we further investigated the presence of yeast Nt-propionylated proteins in vivo. Indeed, we found evidence for Nt-propionylation being a naturally occurring modification in yeast. Interestingly, in a yeast strain lacking NatA, we observed a loss in Nt-propionylation and Nt-acetylation for several NatA substrates, as compared with a control yeast strain expressing endogenous NatA or a strain ectopically expressing hNatA. Thus, besides acting as NATs, yeast and human NatA can act as NPTs and we thus demonstrate for the first time that NATs have the capacity of both acetylating and propionylating protein N-termini in vivo and in vitro.     

Role of Partitioning-defective 1/Microtubule Affinity-regulating Kinases in the Morphogenetic Activity of Helicobacter pylori CagA

Helicobacter pylori CagA plays a key role in gastric carcinogenesis. Upon delivery into gastric epithelial cells, CagA binds and deregulates SHP-2 phosphatase, a bona fide oncoprotein, thereby causing sustained ERK activation and impaired focal adhesions. CagA also binds and inhibits PAR1b/MARK2, one of the four members of the PAR1 family of kinases, to elicit epithelial polarity defect. In nonpolarized gastric epithelial cells, CagA induces the hummingbird phenotype, an extremely elongated cell shape characterized by a rear retraction defect. This morphological change is dependent on CagA-deregulated SHP-2 and is thus thought to reflect the oncogenic potential of CagA. In this study, we investigated the role of the PAR1 family of kinases in the hummingbird phenotype. We found that CagA binds not only PAR1b but also other PAR1 isoforms, with order of strength as follows: PAR1b > PAR1d ≥ PAR1a > PAR1c. Binding of CagA with PAR1 isoforms inhibits the kinase activity. This abolishes the ability of PAR1 to destabilize microtubules and thereby promotes disassembly of focal adhesions, which contributes to the hummingbird phenotype. Consistently, PAR1 knockdown potentiates induction of the hummingbird phenotype by CagA. The morphogenetic activity of CagA was also found to be augmented through inhibition of non-muscle myosin II. Because myosin II is functionally associated with PAR1, perturbation of PAR1-regulated myosin II by CagA may underlie the defect of rear retraction in the hummingbird phenotype. Our findings reveal that CagA systemically inhibits PAR1 family kinases and indicate that malfunctioning of microtubules and myosin II by CagA-mediated PAR1 inhibition cooperates with deregulated SHP-2 in the morphogenetic activity of CagA.Infection with Helicobacter pylori strains bearing cagA (cytotoxin-associated gene A)-positive strains is the strongest risk factor for the development of gastric carcinoma, the second leading cause of cancer-related death worldwide (1–3). The cagA gene is located within a 40-kb DNA fragment, termed the cag pathogenicity island, which is specifically present in the genome of cagA-positive H. pylori strains (4–6). In addition to cagA, there are ∼30 genes in the cag pathogenicity island, many of which encode a bacterial type IV secretion system that delivers the cagA-encoded CagA protein into gastric epithelial cells (7–10). Upon delivery into gastric epithelial cells, CagA is localized to the plasma membrane, where it undergoes tyrosine phosphorylation at the C-terminal Glu-Pro-Ile-Tyr-Ala motifs by Src family kinases or c-Abl kinase (11–14). The C-terminal Glu-Pro-Ile-Tyr-Ala-containing region of CagA is noted for the structural diversity among distinct H. pylori isolates. Oncogenic potential of CagA has recently been confirmed by a study showing that systemic expression of CagA in mice induces gastrointestinal and hematological malignancies (15).When expressed in gastric epithelial cells, CagA induces morphological transformation termed the hummingbird phenotype, which is characterized by the development of one or two long and thin protrusions resembling the beak of the hummingbird. It has been thought that the hummingbird phenotype is related to the oncogenic action of CagA (7, 16–19). Pathophysiological relevance for the hummingbird phenotype in gastric carcinogenesis has recently been provided by the observation that infection with H. pylori carrying CagA with greater ability to induce the hummingbird phenotype is more closely associated with gastric carcinoma (20–23). Elevated motility of hummingbird cells (cells showing the hummingbird phenotype) may also contribute to invasion and metastasis of gastric carcinoma.In host cells, CagA interacts with the SHP-2 phosphatase, C-terminal Src kinase, and Crk adaptor in a tyrosine phosphorylation-dependent manner (16, 24, 25) and also associates with Grb2 adaptor and c-Met in a phosphorylation-independent manner (26, 27). Among these CagA targets, much attention has been focused on SHP-2 because the phosphatase has been recognized as a bona fide oncoprotein, gain-of-function mutations of which are found in various human malignancies (17, 18, 28). Stable interaction of CagA with SHP-2 requires CagA dimerization, which is mediated by a 16-amino acid CagA-multimerization (CM)² sequence present in the C-terminal region of CagA (29). Upon complex formation, CagA aberrantly activates SHP-2 and thereby elicits sustained ERK MAP kinase activation that promotes mitogenesis (30). Also, CagA-activated SHP-2 dephosphorylates and inhibits focal adhesion kinase (FAK), causing impaired focal adhesions. It has been shown previously that both aberrant ERK activation and FAK inhibition by CagA-deregulated SHP-2 are involved in induction of the hummingbird phenotype (31).Partitioning-defective 1 (PAR1)/microtubule affinity-regulating kinase (MARK) is an evolutionally conserved serine/threonine kinase originally isolated in C. elegans (32–34). Mammalian cells possess four structurally related PAR1 isoforms, PAR1a/MARK3, PAR1b/MARK2, PAR1c/MARK1, and PAR1d/MARK4 (35–37). Among these, PAR1a, PAR1b, and PAR1c are expressed in a variety of cells, whereas PAR1d is predominantly expressed in neural cells (35, 37). These PAR1 isoforms phosphorylate microtubule-associated proteins (MAPs) and thereby destabilize microtubules (35, 38), allowing asymmetric distribution of molecules that are involved in the establishment and maintenance of cell polarity.In polarized epithelial cells, CagA disrupts the tight junctions and causes loss of apical-basolateral polarity (39, 40). This CagA activity involves the interaction of CagA with PAR1b/MARK2 (19, 41). CagA directly binds to the kinase domain of PAR1b in a tyrosine phosphorylation-independent manner and inhibits the kinase activity. Notably, CagA binds to PAR1b via the CM sequence (19). Because PAR1b is present as a dimer in cells (42), CagA may passively homodimerize upon complex formation with the PAR1 dimer via the CM sequence, and this PAR1-directed CagA dimer would form a stable complex with SHP-2 through its two SH2 domains.Because of the critical role of CagA in gastric carcinogenesis (7, 16–19), it is important to elucidate the molecular basis underlying the morphogenetic activity of CagA. In this study, we investigated the role of PAR1 isoforms in induction of the hummingbird phenotype by CagA, and we obtained evidence that CagA-mediated inhibition of PAR1 kinases contributes to the development of the morphological change by perturbing microtubules and non-muscle myosin II.