Motivation: Intrinsically Disordered Proteins (IDPs) mediate crucial protein-protein interactions, most notably in signaling and regulation. As their importance is increasingly recognized, the detailed analyses of specific IDP interactions opened up new opportunities for therapeutic targeting. Yet, large scale information about IDP-mediated interactions in structural and functional details are lacking, hindering the understanding of the mechanisms underlying this distinct binding mode. Results: Here, we present DIBS, the first comprehensive, curated collection of complexes between IDPs and ordered proteins. DIBS not only describes by far the highest number of cases, it also provides the dissociation constants of their interactions, as well as the description of potential post-translational modifications modulating the binding strength and linear motifs involved in the binding. Together with the wide range of structural and functional annotations, DIBS will provide the cornerstone for structural and functional studies of IDP complexes. Availability and implementation: DIBS is freely accessible at http://dibs.enzim.ttk.mta.hu/. The DIBS application is hosted by Apache web server and was implemented in PHP. To enrich querying features and to enhance backend performance a MySQL database was also created. Contact: [email protected] or [email protected]. Supplementary information: Supplementary data are available at Bioinformatics online.

MOTIVATION: It is commonplace that intrinsically disordered proteins (IDPs) are involved in crucial interactions in the living cell. However, the study of protein complexes formed exclusively by IDPs is hindered by the lack of data and such analyses remain sporadic. Systematic studies benefited other types of protein-protein interactions paving a way from basic science to therapeutics; yet these efforts require reliable datasets that are currently lacking for synergistically folding complexes of IDPs. RESULTS: Here we present the Mutual Folding Induced by Binding (MFIB) database, the first systematic collection of complexes formed exclusively by IDPs. MFIB contains an order of magnitude more data than any dataset used in corresponding studies and offers a wide coverage of known IDP complexes in terms of flexibility, oligomeric composition and protein function from all domains of life. The included complexes are grouped using a hierarchical classification and are complemented with structural and functional annotations. MFIB is backed by a firm development team and infrastructure, and together with possible future community collaboration it will provide the cornerstone for structural and functional studies of IDP complexes. AVAILABILITY AND IMPLEMENTATION: MFIB is freely accessible at http://mfib.enzim.ttk.mta.hu/. The MFIB application is hosted by Apache web server and was implemented in PHP. To enrich querying features and to enhance backend performance a MySQL database was also created. CONTACT: [email protected], [email protected]. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Lengthy co-evolution of Homo sapiens and Mycobacterium tuberculosis, the main causative agent of tuberculosis, resulted in a dramatically successful pathogen species that presents considerable challenge for modern medicine. The continuous and ever increasing appearance of multi-drug resistant mycobacteria necessitates the identification of novel drug targets and drugs with new mechanisms of action. However, further insights are needed to establish automated protocols for target selection based on the available complete genome sequences. In the present study, we perform complete proteome level comparisons between M. tuberculosis, mycobacteria, other prokaryotes and available eukaryotes based on protein domains, local sequence similarities and protein disorder. We show that the enrichment of certain domains in the genome can indicate an important function specific to M. tuberculosis. We identified two families, termed pkn and PE/PPE that stand out in this respect. The common property of these two protein families is a complex domain organization that combines species-specific regions, commonly occurring domains and disordered segments. Besides highlighting promising novel drug target candidates in M. tuberculosis, the presented analysis can also be viewed as a general protocol to identify proteins involved in species-specific functions in a given organism. We conclude that target selection protocols should be extended to include proteins with complex domain architectures instead of focusing on sequentially unique and essential proteins only.

Intrinsically disordered/unstructured proteins exist without a stable three-dimensional (3D) structure as highly flexible conformational ensembles. The available genome sequences revealed that these proteins are surprisingly common and their frequency reaches high proportions in eukaryotes. Due to their vital role in various biological processes including signaling and regulation and their involvement in various diseases, disordered proteins and protein segments are the focus of many biochemical, molecular biological, pathological and pharmaceutical studies. These proteins are difficult to study experimentally because of the lack of unique structure in the isolated form. Their amino acid sequence, however, is available, and can be used for their identification and characterization by bioinformatic tools, analogously to globular proteins. In this review, we first present a small survey of current methods to identify disordered proteins or protein segments, focusing on those that are publicly available as web servers. In more detail we also discuss approaches that predict disordered regions and specific regions involved in protein binding by modeling the physical background of protein disorder. In our review we argue that the heterogeneity of disordered segments needs to be taken into account for a better understanding of protein disorder.

UNLABELLED: ANCHOR is a web-based implementation of an original method that takes a single amino acid sequence as an input and predicts protein binding regions that are disordered in isolation but can undergo disorder-to-order transition upon binding. The server incorporates the result of a general disorder prediction method, IUPred and can carry out simple motif searches as well. AVAILABILITY: The web server is available at http://anchor.enzim.hu. The program package is freely available for academic users.

Many disordered proteins function via binding to a structured partner and undergo a disorder-to-order transition. The coupled folding and binding can confer several functional advantages such as the precise control of binding specificity without increased affinity. Additionally, the inherent flexibility allows the binding site to adopt various conformations and to bind to multiple partners. These features explain the prevalence of such binding elements in signaling and regulatory processes. In this work, we report ANCHOR, a method for the prediction of disordered binding regions. ANCHOR relies on the pairwise energy estimation approach that is the basis of IUPred, a previous general disorder prediction method. In order to predict disordered binding regions, we seek to identify segments that are in disordered regions, cannot form enough favorable intrachain interactions to fold on their own, and are likely to gain stabilizing energy by interacting with a globular protein partner. The performance of ANCHOR was found to be largely independent from the amino acid composition and adopted secondary structure. Longer binding sites generally were predicted to be segmented, in agreement with available experimentally characterized examples. Scanning several hundred proteomes showed that the occurrence of disordered binding sites increased with the complexity of the organisms even compared to disordered regions in general. Furthermore, the length distribution of binding sites was different from disordered protein regions in general and was dominated by shorter segments. These results underline the importance of disordered proteins and protein segments in establishing new binding regions. Due to their specific biophysical properties, disordered binding sites generally carry a robust sequence signal, and this signal is efficiently captured by our method. Through its generality, ANCHOR opens new ways to study the essential functional sites of disordered proteins.

UNLABELLED: The TOPDOM database is a collection of domains and sequence motifs located consistently on the same side of the membrane in alpha-helical transmembrane proteins. The database was created by scanning well-annotated transmembrane protein sequences in the UniProt database by specific domain or motif detecting algorithms. The identified domains or motifs were added to the database if they were uniformly annotated on the same side of the membrane of the various proteins in the UniProt database. The information about the location of the collected domains and motifs can be incorporated into constrained topology prediction algorithms, like HMMTOP, increasing the prediction accuracy. AVAILABILITY: The TOPDOM database and the constrained HMMTOP prediction server are available on the page http://topdom.enzim.hu CONTACT: [email protected]; [email protected].

The Mediator complex provides an interface between gene-specific regulatory proteins and the general transcription machinery including RNA polymerase II (RNAP II). The complex has a modular architecture (Head, Middle, and Tail) and cryoelectron microscopy analysis suggested that it undergoes dramatic conformational changes upon interactions with activators and RNAP II. These rearrangements have been proposed to play a role in the assembly of the preinitiation complex and also to contribute to the regulatory mechanism of Mediator. In analogy to many regulatory and transcriptional proteins, we reasoned that Mediator might also utilize intrinsically disordered regions (IDRs) to facilitate structural transitions and transmit transcriptional signals. Indeed, a high prevalence of IDRs was found in various subunits of Mediator from both Saccharomyces cerevisiae and Homo sapiens, especially in the Tail and the Middle modules. The level of disorder increases from yeast to man, although in both organisms it significantly exceeds that of multiprotein complexes of a similar size. IDRs can contribute to Mediator's function in three different ways: they can individually serve as target sites for multiple partners having distinctive structures; they can act as malleable linkers connecting globular domains that impart modular functionality on the complex; and they can also facilitate assembly and disassembly of complexes in response to regulatory signals. Short segments of IDRs, termed molecular recognition features (MoRFs) distinguished by a high protein-protein interaction propensity, were identified in 16 and 19 subunits of the yeast and human Mediator, respectively. In Saccharomyces cerevisiae, the functional roles of 11 MoRFs have been experimentally verified, and those in the Med8/Med18/Med20 and Med7/Med21 complexes were structurally confirmed. Although the Saccharomyces cerevisiae and Homo sapiens Mediator sequences are only weakly conserved, the arrangements of the disordered regions and their embedded interaction sites are quite similar in the two organisms. All of these data suggest an integral role for intrinsic disorder in Mediator's function.

MOTIVATION: The dynamic nature of protein interaction networks requires fast and transient molecular switches. The underlying recognition motifs (linear motifs, LMs) are usually short and evolutionarily variable segments, which in several cases, such as phosphorylation sites or SH3-binding regions, fall into locally disordered regions. We probed the generality of this phenomenon by predicting the intrinsic disorder of all LM-containing proteins enlisted in the Eukaryotic Linear Motif (ELM) database. RESULTS: We demonstrated that LMs in average are embedded in locally unstructured regions, while their amino acid composition and charge/hydropathy properties exhibit a mixture characteristic of folded and disordered proteins. Overall, LMs are constructed by grafting a few specificity-determining residues favoring structural order on a highly flexible carrier region. These results establish a connection between LMs and molecular recognition elements of intrinsically unstructured proteins (IUPs), which realize a non-conventional mode of partner binding mostly in regulatory functions.

BACKGROUND: A large number of PCR primer-design softwares are available online. However, only very few of them can be used for the design of primers to amplify bisulfite-treated DNA templates, necessary to determine genomic DNA methylation profiles. Indeed, the number of studies on bisulfite-treated templates exponentially increases as determining DNA methylation becomes more important in the diagnosis of cancers. Bisulfite-treated DNA is difficult to amplify since undesired PCR products are often amplified due to the increased sequence redundancy after the chemical conversion. In order to increase the efficiency of PCR primer-design, we have developed BiSearch web server, an online primer-design tool for both bisulfite-treated and native DNA templates. RESULTS: The web tool is composed of a primer-design and an electronic PCR (ePCR) algorithm. The completely reformulated ePCR module detects potential mispriming sites as well as undesired PCR products on both cDNA and native or bisulfite-treated genomic DNA libraries. Due to the new algorithm of the current version, the ePCR module became approximately hundred times faster than the previous one and gave the best performance when compared to other web based tools. This high-speed ePCR analysis made possible the development of the new option of high-throughput primer screening. BiSearch web server can be used for academic researchers at the http://bisearch.enzim.hu site. CONCLUSION: BiSearch web server is a useful tool for primer-design for any DNA template and especially for bisulfite-treated genomes. The ePCR tool for fast detection of mispriming sites and alternative PCR products in cDNA libraries and native or bisulfite-treated genomes are the unique features of the new version of BiSearch software.

Summary: Intrinsically unstructured/disordered proteins and domains (IUPs) lack a well-defined three-dimensional structure under native conditions. The IUPred server presents a novel algorithm for predicting such regions from amino acid sequences by estimating their total pairwise interresidue interaction energy, based on the assumption that IUP sequences do not fold due to their inability to form sufficient stabilizing interresidue interactions. Optional to the prediction are built-in parameter sets optimized for predicting short or long disordered regions and structured domains. Availability: The IUPred server is available for academic users at http://iupred.enzim.hu Contact: [email protected]

The structure of integral membrane proteins is determined in the absence of the lipid bilayer; consequently the membrane localization of the protein is usually not specified in the corresponding PDB file. Recently, we have developed a new method called TMDET which determines the most possible localization of the membrane relative to the protein structure, and gives the annotation of the membrane embedded parts of the sequence. The entire Protein Data Bank has been scanned by the new TMDET algorithm resulting in the database of structurally determined transmembrane proteins (PDB_TM). Here we present the web interface of the TMDET algorithm to allow scientists to determine the membrane localization of structural data prior to deposition or to analyze model structures.

UNLABELLED: Web-based servers implementing the DAS-TMfilter algorithm have been launched at three mirror sites and their usage is described. The underlying computer program is an upgraded and modified version of the DAS-prediction method. The new server is (approximately 1 among 100 unrelated queries) while the high efficiency of the original algorithm locating TM segments in queries is preserved (sensitivity of approximately 95% among documented proteins with helical TM regions). AVAILABILITY: The server operates at three mirror sites: http://mendel.imp.univie.ac.at/sat/DAS/DAS.html, http://wooster.bip.bham.ac.uk/DAS.html and http://www.enzim.hu/DAS/DAS.html. The program is available on request.

MOTIVATION: Integral membrane proteins play important roles in living cells. Although these proteins are estimated to constitute 25% of proteins at a genomic scale, the Protein Data Bank (PDB) contains only a few hundred membrane proteins due to the difficulties with experimental techniques. The presence of transmembrane proteins in the structure data bank, however, is quite invisible, as the annotation of these entries is rather poor. Even if a protein is identified as a transmembrane one, the possible location of the lipid bilayer is not indicated in the PDB because these proteins are crystallized without their natural lipid bilayer, and currently no method is publicly available to detect the possible membrane plane using the atomic coordinates of membrane proteins. RESULTS: Here, we present a new geometrical approach to distinguish between transmembrane and globular proteins using structural information only and to locate the most likely position of the lipid bilayer. An automated algorithm (TMDET) is given to determine the membrane planes relative to the position of atomic coordinates, together with a discrimination function which is able to separate transmembrane and globular proteins even in cases of low resolution or incomplete structures such as fragments or parts of large multi chain complexes. This method can be used for the proper annotation of protein structures containing transmembrane segments and paves the way to an up-to-date database containing the structure of all known transmembrane proteins and fragments (PDB_TM) which can be automatically updated. The algorithm is equally important for the purpose of constructing databases purely of globular proteins.

SUMMARY: SCide is a program to identify stabilization centers from known protein structures. These are residues involved in cooperative long-range contacts, which can be formed between various regions of a single polypeptide chain, or they can belong to different peptides or polypeptides in a complex. The server takes a PDB file as an input, and the result is presented in graphical or text format. AVAILABILITY: SCide is available on the web at http://www.enzim.hu/scide. The source code can be obtained from the authors on request.

UNLABELLED: The HMMTOP transmembrane topology prediction server predicts both the localization of helical transmembrane segments and the topology of transmembrane proteins. Recently, several improvements have been introduced to the original method. Now, the user is allowed to submit additional information about segment localization to enhance the prediction power. This option improves the prediction accuracy as well as helps the interpretation of experimental results, i.e. in epitope insertion experiments. AVAILABILITY: HMMTOP 2.0 is freely available to non-commercial users at http://www.enzim.hu/hmmtop. Source code is also available upon request to academic users.

MOTIVATION: Protein sequences found in databanks usually do not report post translational covalent modifications such as the oxidation state of cystein (Cys) residues. Accurate prediction of whether a functionally or structurally important Cys occurs in the oxidized or thiol form would be helpful for molecular biology experiments and structure prediction. RESULTS: A new method is presented for predicting the oxidation state of Cys residues based on multiple sequence alignments and on the observation that Cys tends to occur in the same oxidation state within the same protein. The prediction of the redox state of Cys performs above 82%. The oxidation state of Cys correlates with the cellular location of the given protein within the cell, but the correlation is not perfect (up to 70%). We also perform a statistical analysis of the different redox states of Cys found in secondary structures and buried positions, and of the secondary structures linked by disulfide bonds. The results suggest that the natural borderline lies between the different oxidation states of Cys rather than between the half cystines and cysteins. AVAILABILITY: A web server implementing the prediction method is available at http://guitar.rockefeller.edu/approximately andras/cyspred.html CONTACT: [email protected]

MOTIVATION: Secondary structure predictions based on the properties of individual residues, and sometimes on local interactions, usually fail to exceed 65% efficiency. Therefore, non-local, long-range interactions seem to be a significant cause of this limitation. RESULTS: In this paper, we apply approaches to localize highly interacting residues and clusters of residues involved in multiple non-local interactions, and test various secondary structure predictions on this separate subset to assess the effect of long-range interactions on the prediction efficiencies. It was found that only a marginal part of the failure of secondary structure predictions results from the presence of long-range interactions. Alternative possibilities are also discussed.

During the winter qnarter of 1992 two highresohstion color workstations and projecting equipment were installed in a classroom in the School of Science.We describe this classroom computing environment, our experience using it in Computer Science instruction, and some novel instructional software used in the facility.

A number of open questions are settled about the expected costs of two disjoint set Union and Find algorithms raised by Knuth and Schönhage [Theoret. Comput. Sci., 6 (1978), pp. 281–315]. This paper shows that the expected time of the Weighted Quick-Find (QFW) algorithm to perform $(n - 1)$ randomly chosen unions is $cn + o({n / {\log n}})$, where $c = 2.0847 \ldots $ . Through an observation of Tarjan and Van Leeuwen in [J. Assoc. Comput. Mach., 22 (1975), pp. 215–225] this implies linear time bounds to perform $O(n)$ unions and finds for a class of other union-find algorithms. It is also proved that the expected time of the Unweighted Quick-Find (QF) algorithm is ${{n^2 } / {8 + O(n(\log n)^2 )}}$. The expected costs of QFW and QF are analyzed when fewer than $(n - 1)$ unions are performed. Among other results, for QFW it is shown that the expected cost of $m = o(n)$ randomly chosen unions is $m(1 + o(1))$. If $m = {{\alpha n} / 2}$, where $\alpha \leqslant e^{ - 2} $, this cost is $m(1 + \epsilon (\alpha ) + o(1))$, where $\epsilon (\alpha ) \to 0$ as $\alpha \to 0$ and $\epsilon (e^{ - 2} ) \leqslant .026$. For QF, the expected cost of ${n / {2 - n^{{2 / 3}} }}(\log n)^{{2 / 3}} $ randomly chosen unions is $O(n\log n)$.

A new approach to the analysis of random probing hashing algorithms is presented. The probability-generating function in closed form for the asymptotic cost of insertion via random probing with secondary clustering is derived. For higher-order clustering, it is shown that all the moments of the probability distribution of the insertion cost exist and are asymptotically equal to the corresponding moments of the cost distribution under uniform hashing. The method in this paper also leads to simple derivations for the expected cost of insertion for random probing with secondary and higher-order clustering.

We show that the expected time of the Weighted Quickfind (QFW) disjoint set union and find algorithm to perform (n - 1) randomly chosen unions is cn + o(n/log n), where c = 2.0847 …. This implies, through an observation of Tarjan and Van Leeuwen, linear expected time bounds to perform O(n) unions and finds for a class of other union -find algorithms. We also prove that the expected time of the unweighted Quickfind (QF) algorithm is n2/8 + o(n(log n)2), and set the several related open questions of Knuth and Schönhage.

@ NP then ≤mP and ≤TP differ on NP. One method that might prove helpful in settling this conjecture is to exhibit an efficient construction that builds from any nonpolynomial set A a set B such that A ≤TP B but A

The average number of levels that a new element moves up when inserted into a heap is investigated. Two probabilistic models under which such an average might be computed are proposed. A `Lemma of Conservation of Ignorance' is formulated and used in the derivation of an exact formula for the average in one of these models. It is shown that this average is bounded by a constant and its asymptotic behaviour is discussed. Numerical data for the second model are also provided and analyzed.