218 research outputs found
Safe Functional Inference for Uncharacterized Viral Proteins
No full textThe explosive growth in the number of sequenced genomes has created a flood of protein sequences with unknown structure and function. A routine protocol for functional inference on an input query sequence is based on a database search for homologues. Searching a query against a non-redundant database using BLAST (or more advanced methods, e.g. PSI-BLAST) suffers from several drawbacks: (i) a local alignment often dominates the results; (ii) the reported statistical score (i.e. E-value) is often misleading; (iii) incorrect annotations may be falsely propagated. 
Several systematic methods are commonly used to assign sequences with functions on a genomic scale. In Pfam (1) and resources alike, statistical profiles (HMMs) are built from semi-manual multiple alignments of seed homologous sequences. The profiles are then used to scan genomic sequences for additional family members. The drawbacks of this scheme are: (i) only families with a predetermined seed are considered; (ii) the query must have a detectable sequence similarity to seed sequences; (iii) attention to internal relationships among the family members or the relations to other families is lacking; (iv) family membership is often set by pre-determined thresholds.
An alternative to profile or model based methods for functional inference relies on a hierarchical clustering of the protein space, as implemented in the ProtoNet approach (2). The fundamental principle is the creation of a tree that captures evolutionary relatedness among protein families. The tree construction is fully automatic, and is based only on reported BLAST similarities among clustered sequences. The tree provides protein groupings in continuous evolutionary granularities, from closely related to distant superfamilies. Clusters in the ProtoNet tree show high correspondence with homologous sequence (i.e. Pfam and InterPro), functional (i.e. E.C. classification) and structural (i.e., SCOP) families (3). A new clustering scheme (4) has provided an extensive update to the ProtoNet process, which is now based on direct clustering of all detectable sequence similarities. 
Herein, we use the ProtoNet resource to develop a methodology for a consistent and safe functional inference for remote families. We illustrate the success of our approach towards clusters of poorly characterized viral proteins. Viral sequences are characterized by a rapid evolutionary rate which drives viral families to be even more remote (sequence-similarity-wise). Thus, functional inference for viral families is apparently an unsolved task. Despite this inherent difficulty, the new ProtoNet tree scaffold reliably captures weak evolutionary connections for viral families, which were previously overlooked. We take advantage of this, and propose new functional assignments for viral protein families.

08101 Abstracts Collection – Computational Proteomics
No full textThe second Dagstuhl Seminar on emph{Computational Proteomics} took place
from March 3rd to 7th, 2008 in Schloss Dagstuhl--Leibniz Center for
Informatics. This highly international meeting brought together researchers
from computer science and from proteomics to discuss the state of the art
and future developments at the interface between experiment and theory.
This interdisciplinary exchange covered a wide range of topics, from new
experimental methods resulting in more complex data we will have to expect
in the future to purely theoretical studies of what level of experimental
accuracy is required in order to solve certain problems. A particular focus
was also on the application side, where the participants discussed more
complex experimental methodologies that are enabled by more sophisticated
computational techniques. Quantitative aspects of protein expression
analysis as well as posttranslational modifications in the context of
disease development and diagnosis were discussed. The seminar sparked a
number of new ideas and collaborations and has resulted in several joint
grant applications and paper submissions.
This paper describes the seminar topics, its goals and results. The
executive summary is followed by the abstracts of the presentations given.
Links to extended abstracts or full papers are provided, if available
Characteristic polynomials of Linial arrangements for exceptional root systems
No full textThe (extended) Linial arrangement L-Phi(m) is a certain finite truncation of the affine Weyl arrangement of a root system with a parameter m. Postnikov and Stanley conjectured that all roots of the characteristic polynomial of L-Phi(m) have the same real part, and this has been proved for the root systems of classical types. In this paper we prove that the conjecture is true for exceptional root systems when the parameter m is sufficiently large. The proof is based on representations of the characteristic quasi-polynomials in terms of Eulerian polynomials
The Secrets of a Functional Synapse – From a Computational and Experimental Viewpoint
No full textAbstract Background Neuronal communication is tightly regulated in time and in space. The neuronal transmission takes place in the nerve terminal, at a specialized structure called the synapse. Following neuronal activation, an electrical signal triggers neurotransmitter (NT) release at the active zone. The process starts by the signal reaching the synapse followed by a fusion of the synaptic vesicle and diffusion of the released NT in the synaptic cleft; the NT then binds to the appropriate receptor, and as a result, a potential change at the target cell membrane is induced. The entire process lasts for only a fraction of a millisecond. An essential property of the synapse is its capacity to undergo biochemical and morphological changes, a phenomenon that is referred to as synaptic plasticity. Results In this survey, we consider the mammalian brain synapse as our model. We take a cell biological and a molecular perspective to present fundamental properties of the synapse:(i) the accurate and efficient delivery of organelles and material to and from the synapse; (ii) the coordination of gene expression that underlies a particular NT phenotype; (iii) the induction of local protein expression in a subset of stimulated synapses. We describe the computational facet and the formulation of the problem for each of these topics. Conclusion Predicting the behavior of a synapse under changing conditions must incorporate genomics and proteomics information with new approaches in computational biology.</p
Congestion Games with Failures - CGFs
No full textWe introduce a new class of games---congestion games with failures (CGFs), which extends the class of congestion games to allow for facility failures. In a basic CGF (BCGF) agents share a common set of facilities (service providers), where each service provider (SP) may fail with some known probability. For reliability reasons, an agent may choose a subset of the SPs in order to try and perform his task. The cost of an agent for utilizing any SP is a function of the total number of agents using this SP. A main feature of this setting is that the cost for an agent for successful completion of his task is the minimum of the costs of his successful attempts. We show that although BCGFs do not admit a potential function, and thus are not isomorphic to classic congestion games, they always possess a pure-strategy Nash equilibrium. We also show that the SPs' congestion experienced in different Nash equilibria is (almost) unique. For the subclass of symmetric BCGFs we give a characterization of best and worst Nash equilibria. We extend the basic model by making task submission costly and define a model for taxed CGFs (TCGFs). We prove the existence of a pure-strategy Nash equilibrium for quasi-symmetric TCGFs, and present an efficient algorithm for constructing such Nash equilibrium in symmetric TCGFs
The Metric Space of Proteins: Comparative Study of Clustering Algorithms
No full textThis article appears in: Proceedings of the Tenth International Conference on Intelligent Systems for Molecular Biolog
BMC Bioinformatics Methodology article EVEREST: automatic identification and classification of protein
No full textBackground: Proteins are comprised of one or several building blocks, known as domains. Such domains can be classified into families according to their evolutionary origin. Whereas sequencing technologies have advanced immensely in recent years, there are no matching computational methodologies for large-scale determination of protein domains and their boundaries. We provide and rigorously evaluate a novel set of domain families that is automatically generated from sequence data. Our domain family identification process, called EVEREST (EVolutionary Ensembles of REcurrent SegmenTs), begins by constructing a library of protein segments that emerge in an all vs. all pairwise sequence comparison. It then proceeds to cluster these segments into putative domain families. The selection of the best putative families is done using machine learning techniques. A statistical model is then created for each of the chosen families. This procedure is then iterated: the aforementioned statistical models are used to scan all protein sequences, to recreate a library of segments and to cluster them again. Results: Processing the Swiss-Prot section of the UniProt Knoledgebase, release 7.2, EVEREST defines 20,230 domains, covering 85 % of the amino acids of the Swiss-Prot database. EVERES
- …
