Multiple consensus trees: a method to separate divergent genes.

BACKGROUND: It is generally admitted that the species tree cannot be inferred from the genetic sequences of a single gene because the evolution of different genes, and thus the gene tree topologies, may vary substantially. Gene trees can differ, for example, because of horizontal transfer events or because some of them correspond to paralogous instead of orthologous sequences. A variety of methods has been proposed to tackle the problem of the reconciliation of gene trees in order to reconstruct a species tree. When the taxa in all the trees are identical, the problem can be stated as a consensus tree problem. RESULTS: In this paper we define a new method for deciding whether a unique consensus tree or multiple consensus trees can best represent a set of given phylogenetic trees. If the given trees are all congruent, they should be compatible into a single consensus tree. Otherwise, several consensus trees corresponding to divergent genetic patterns can be identified. We introduce a method optimizing the generalized score, over a set of tree partitions in order to decide whether the given set of gene trees is homogeneous or not. CONCLUSIONS: The proposed method has been validated with simulated data (random trees organized in three topological groups) as well as with real data (bootstrap trees, homogeneous set of trees, and a set of non homogeneous gene trees of 30 E. Coli strains; it is worth noting that some of the latter genes underwent horizontal gene transfers). A computer program, MCT - Multiple Consensus Trees, written in C was made freely available for the research community (it can be downloaded from http://bioinformatics.lif.univ-mrs.fr/consensus/index.html). It handles trees in a standard Newick format, builds three hierarchies corresponding to RF and QS similarities between trees and the greedy ascending algorithm. The generalized score values of all tree partitions are computed.

Multifunctional proteins revealed by overlapping clustering in protein interaction network.

MOTIVATION: Multifunctional proteins perform several functions. They are expected to interact specifically with distinct sets of partners, simultaneously or not, depending on the function performed. Current graph clustering methods usually allow a protein to belong to only one cluster, therefore impeding a realistic assignment of multifunctional proteins to clusters. RESULTS: Here, we present Overlapping Cluster Generator (OCG), a novel clustering method which decomposes a network into overlapping clusters and which is, therefore, capable of correct assignment of multifunctional proteins. The principle of OCG is to cover the graph with initial overlapping classes that are iteratively fused into a hierarchy according to an extension of Newman's modularity function. By applying OCG to a human protein-protein interaction network, we show that multifunctional proteins are revealed at the intersection of clusters and demonstrate that the method outperforms other existing methods on simulated graphs and PPI networks. AVAILABILITY: This software can be downloaded from http://tagc.univ-mrs.fr/welcome/spip.php?rubrique197 CONTACT: brun@tagc.univ-mrs.fr SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

Clustering proteins from interaction networks for the prediction of cellular functions.

BACKGROUND: Developing reliable and efficient strategies allowing to infer a function to yet uncharacterized proteins based on interaction networks is of crucial interest in the current context of high-throughput data generation. In this paper, we develop a new algorithm for clustering vertices of a protein-protein interaction network using a density function, providing disjoint classes. RESULTS: Applied to the yeast interaction network, the classes obtained appear to be biological significant. The partitions are then used to make functional predictions for uncharacterized yeast proteins, using an annotation procedure that takes into account the binary interactions between proteins inside the classes. We show that this procedure is able to enhance the performances with respect to previous approaches. Finally, we propose a new annotation for 37 previously uncharacterized yeast proteins. CONCLUSION: We believe that our results represent a significant improvement for the inference of cellular functions, that can be applied to other organism as well as to other type of interaction graph, such as genetic interactions.

Clust&See: a Cytoscape plugin for the identification, visualization and manipulation of network clusters.

BACKGROUND AND SCOPE: Large networks, such as protein interaction networks, are extremely difficult to analyze as a whole. We developed Clust&See, a Cytoscape plugin dedicated to the identification, visualization and analysis of clusters extracted from such networks. IMPLEMENTATION AND PERFORMANCE: Clust&See provides the ability to apply three different, recently developed graph clustering algorithms to networks and to visualize: (i) the obtained partition as a quotient graph in which nodes correspond to clusters and (ii) the obtained clusters as their corresponding subnetworks. Importantly, tools for investigating the relationships between clusters and vertices as well as their organization within the whole graph are supplied.

Defining a modular signalling network from the fly interactome.

BACKGROUND: Signalling pathways relay information by transmitting signals from cell surface receptors to intracellular effectors that eventually activate the transcription of target genes. Since signalling pathways involve several types of molecular interactions including protein-protein interactions, we postulated that investigating their organization in the context of the global protein-protein interaction network could provide a new integrated view of signalling mechanisms. RESULTS: Using a graph-theory based method to analyse the fly protein-protein interaction network, we found that each signalling pathway is organized in two to three different signalling modules. These modules contain canonical proteins of the signalling pathways, known regulators as well as other proteins thereby predicted to participate to the signalling mechanisms. Connections between the signalling modules are prominent as compared to the other network's modules and interactions within and between signalling modules are among the more central routes of the interaction network. CONCLUSION: Altogether, these modules form an interactome sub-network devoted to signalling with particular topological properties: modularity, density and centrality. This finding reflects the integration of the signalling system into cell functioning and its important role connecting and coordinating different biological processes at the level of the interactome.

PRODISTIN Web Site: a tool for the functional classification of proteins from interaction networks.

UNLABELLED: The PRODISTIN Web Site is a web service allowing users to functionally classify genes/proteins from any type of interaction network. The resulting computation provides a classification tree in which (1) genes/proteins are clustered according to the identity of their interaction partners and (2) functional classes are delineated in the tree using the Biological Process Gene Ontology annotations. AVAILABILITY: The PRODISTIN Web Site is freely accessible at http://gin.univ-mrs.fr/webdistin

Approach of the functional evolution of duplicated genes in Saccharomyces cerevisiae using a new classification method based on protein-protein interaction data.

The concept of protein function is widely used and manipulated by biologists. However, the means of the concept and its understanding may vary depending on the level of functionality one considers (molecular, cellular, physiological, etc.). Genomic studies and new high-throughput methods of the post-genomic era provide the opportunity to shed a new light on the concept of protein function: protein-protein interactions can now be considered as pieces of incomplete but still gigantic networks and the analysis of these networks will permit the emergence of a more integrated view of protein function. In this context, we propose a new functional classification method, which, unlike usual methods based on sequence homology, allows the definition of functional classes of protein based on the identity of their interacting partners. An example of such classification will be shown and discussed for a subset of Saccharomyces cerevisiae proteins, accounting for 7% of the yeast proteome. The genome of the budding yeast contains 50% of protein-coding genes that are paralogs, including 457 pairs of duplicated genes coming probably from an ancient whole genome duplication. We will comment on the functional classification of the duplicated genes when using our method and discuss the contribution of these results to the understanding of function evolution for the duplicated genes.

Functional classification of proteins for the prediction of cellular function from a protein-protein interaction network.

We here describe PRODISTIN, a new computational method allowing the functional clustering of proteins on the basis of protein-protein interaction data. This method, assessed biologically and statistically, enabled us to classify 11% of the Saccharomyces cerevisiae proteome into several groups, the majority of which contained proteins involved in the same biological process(es), and to predict a cellular function for many otherwise uncharacterized proteins.