Community detection in complex networks : Application to gene interaction network ; Détection de communautés dans les grands réseaux : Application aux réseaux d'interactions de gènes

In our work, we are interested in the communities' detection in protein-protein interaction networks (PPI). Thesecommunities give us an idea about the perception of the network’s structure. One of the goals in biology is todetermine how genes or proteins encode function in the cell. This work is multidisciplinary, as it brings the field ofbiology and computer science in the broad sense. Thus, our objectif is to find communities of genes having abiological sense (that participate in the same biological processes or that perform together specific biologicalfunctions) from gene annotation sources. To make this task, we have combined three levels of information : i)Semantic level: information contained in biological ontologies such as Gene Ontology (GO) and informationobtained by the use of a similarity measure such as GO-based similarity of gene sets (GS2). It assesses thesemantic similarity between genes, ii) Functional level: information contained in public databases describing theinteractions of genes iii) Networks level: information contained in pathway databases. Our work has four parts.The first part focuses on the extraction of biological data used in our project. Thus, we study the semantic similaritybetween groups of genes that are annotated by terms of biological ontology. It is one of the characteristics of agene community. The second part present the proposed approach GA-PPI-Net for the detection of genecommunities. It is a Genetic Algorithm based approach to detect communities having different sizes from PPInetworks. For this purpose, we use a fitness function based on a similarity measure and the interaction valuebetween proteins or genes. Moreover, a specific solution for representing a community and a specific mutationoperator are introduced. The third part presents two extensions of GA-PPI-Net. The first one proposes a specificadaptive mutation operator. The second aims to make GA-PPI-Net generic by allowing finding different sizes ofcommunities based on the interaction and/or similarity criterion. ...