Detecting network communities: an application to phylogenetic analysis.

This paper proposes a new method to identify communities in generally weighted complex networks and apply it to phylogenetic analysis. In this case, weights correspond to the similarity indexes among protein sequences, which can be used for network construction so that the network structure can be analyzed to recover phylogenetically useful information from its properties. The analyses discussed here are mainly based on the modular character of protein similarity networks, explored through the Newman-Girvan algorithm, with the help of the neighborhood matrix . The most relevant networks are found when the network topology changes abruptly revealing distinct modules related to the sets of organisms to which the proteins belong. Sound biological information can be retrieved by the computational routines used in the network approach, without using biological assumptions other than those incorporated by BLAST. Usually, all the main bacterial phyla and, in some cases, also some bacterial classes corresponded totally (100%) or to a great extent (>70%) to the modules. We checked for internal consistency in the obtained results, and we scored close to 84% of matches for community pertinence when comparisons between the results were performed. To illustrate how to use the network-based method, we employed data for enzymes involved in the chitin metabolic pathway that are present in more than 100 organisms from an original data set containing 1,695 organisms, downloaded from GenBank on May 19, 2007. A preliminary comparison between the outcomes of the network-based method and the results of methods based on Bayesian, distance, likelihood, and parsimony criteria suggests that the former is as reliable as these commonly used methods. We conclude that the network-based method can be used as a powerful tool for retrieving modularity information from weighted networks, which is useful for phylogenetic analysis.

Comparative protein analysis of the chitin metabolic pathway in extant organisms: a complex network approach.

Chitin is a structural endogenous carbohydrate, which is a major component of fungal cell walls and arthropod exoskeletons. A renewable resource and the second most abundant polysaccharide in nature after cellulose, chitin is currently used for waste water clearing, cosmetics, medical, and veterinary applications. This work comprises data mining of protein sequences related to the chitin metabolic pathway of completely sequenced genomes of extant organisms pertaining to the three life domains, followed by meta-analysis using traditional sequence similarity comparison and complex network approaches. Complex networks involving proteins of the chitin metabolic pathway in extant organisms were constructed based on protein sequence similarity. Several usual network indices were estimated in order to obtain information on the topology of these networks, including those related to higher order neighborhood properties. Due to the assumed evolutionary character of the system, we also discuss issues related to modularity properties, with the concept of edge betweenness playing a particularly important role in our analysis. Complex network approach correctly identifies clusters of organisms that belong to phylogenetic groups without any a priori knowledge about the biological features of the investigated protein sequences. We envisage the prospect of using such a complex network approach as a high-throughput phylogenetic method.

Neighborhood properties of complex networks.

A concept of neighborhood in complex networks is addressed based on the criterion of the minimal number of steps to reach other vertices. This amounts to, starting from a given network R1, generating a family of networks Rl, l = 2, 3,... such that, the vertices that are l steps apart in the original R1, are only 1 step apart in Rl. The higher order networks are generated using Boolean operations among the adjacency matrices Ml that represent Rl. The families originated by the well known linear and the Erdös-Renyi networks are found to be invariant, in the sense that the spectra of Ml are the same, up to finite size effects. A further family originated from small world network is identified.