Biological sub-graph identification thanks to metaheuristics

Type de poste
Niveau d'étude minimal
Durée du poste
Contrat renouvelable
Contrat non renouvelable
Date de prise de fonction
Date de fin de validité de l'annonce
Nom de la structure d'accueil

Laboratoire d'Informatique Signaux et Systèmes (UMR7271)
CS 40121
06903 Sophia Antipolis

Denis Pallez
Claude Pasquier
Email du/des contacts

PhD Position on "Biological sub-graph identification thanks to metaheuristics" at the I3S laboratory ( in Sophia-Antipolis.

Application: a curiculum vitae and a motivation letter should be sent to Claude Pasquier ( and Denis Pallez ( before 19th May 2019.

Context: According to World Health Organization, cancer is the second leading cause of death globally, and is responsible for around 10 million deaths in 2018. The most common one is lung cancer responsible of more than 2 million cases. Two classes of lung cancer exists which grow and spread differently in patients. Treatment options depend mainly on the type and stage of the cancer (Lemjabbar-Alaoui et al., 2015). In order to develop more efficacious and more specific drugs, scientists must better understand complex biological systems related to this cancer. For this reason, biological networks - containing functional interactions between genes, proteins, DNAs, RNAs… - have been created by biologists and stored in public databases. For instance, graphs with human genes as nodes and interactions between nodes as edges are considered. For understanding disease mechanisms, active module (i.e. well-connected subnetworks that significantly and collaboratively react to certain conditions) are mined in one or more biological networks at a time. To each condition is associated a score, a mathematical function. The problem of finding optimal subnetworks with the highest score is NP-hard. Main computational methods for solving the active subnetworks identification problem (Nguyen et al., 2019) are (i) greedy algorithms, (ii) random walk algorithms, (iii) diffusion emulation models, (iv) genetic algorithms, (v) maximal clique identification and (vi) clustering based methods. First two methods are simple and rapid but are highly dependent to the starting point of the algorithm that does not guarantee to reach global optima. Conversely, methods (iii) and (iv) are able to find global optima or an approximation of it at the prize of a computational burden. Finally, methods (v) and (vi) do not fully answer to the initial issue as it is not true that all genes of the resulting clique take part in the biological process or as number of genes in optimal cluster is too huge for being understandable.

Objectives: Nevertheless, all previous methods only consider static information without taking into account the kinetic interactions that exist in biological systems. That is why we are interested, in this work, to build a memetic algorithm (Cotta et al., 2018) that combines a global search technique with a local search technique for active module identification in a multi-objective and dynamic context. Scalable benchmarks can be used for testing (Jiang et al., 2019).

Skills and profile:

  • Master degree in Computer Science, especially in Optimization and/or Data Mining
  • Programming skills are needed
  • Knowledge in Bioinformatics could be a great help
  • Oral and written english is required. French is not mandatory.



Cotta, C., Mathieson, L., Moscato, P., 2018. Memetic Algorithms, in: Martí, R., Pardalos, P.M., Resende, M.G.C. (Éd.), Handbook of Heuristics. Springer International Publishing, Cham, p. 607‑638.

Jiang, S., Kaiser, M., Yang, S., Kollias, S., Krasnogor, N., 2019. A Scalable Test Suite for Continuous Dynamic Multiobjective Optimization. IEEE Trans. Cybern. 1‑13. Lemjabbar-Alaoui, H., Hassan, O.U., Yang, Y.-W., Buchanan, P., 2015. Lung cancer: Biology and treatment options. Biochim. Biophys. Acta 1856, 189‑210.

Nguyen, H., Shrestha, S., Tran, D., Shafi, A., Draghici, S., Nguyen, T., 2019. A Comprehensive Survey of Tools and Software for Active Subnetwork Identification. Front. Genet. 10.

Equipe adhérente personne morale SFBI
Equipe Non adhérente