Skip to Main content Skip to Navigation

Aspects algorithmiques de la comparaison d'éléments biologiques

Abstract : To investigate the complex links between genotype and phenotype, one can study the relations between different biological entities. It forms a biological network, represented by a graph. In this thesis, we are interested in the occurrence of a motif (a multi-set of colors) in a vertex-colored graph, representing a biological network. Such motifs usually correspond to a set of elements realizing a same function, and which may have been evolutionarily preserved. We follow the algorithmic study of this problem, by establishing hard instances and studying possibilities to cope with the hardness (parameterized complexity, preprocessing, approximation...). We also develop a plugin for Cytoscape, in order to solve efficiently this problem and to test it on real data.We are also interested in different problems related to comparative genomics. The scientific method is the same: studying problems arising from biology, specifying the hard instances and giving solutions to cope with the hardness (or proving such solutions are unlikely)
Document type :
Complete list of metadata

Cited literature [177 references]  Display  Hide  Download
Contributor : ABES STAR :  Contact
Submitted on : Wednesday, February 8, 2012 - 1:29:22 PM
Last modification on : Saturday, January 15, 2022 - 3:57:07 AM
Long-term archiving on: : Wednesday, May 9, 2012 - 2:35:16 AM


Version validated by the jury (STAR)


  • HAL Id : pastel-00667797, version 1


Florian Sikora. Aspects algorithmiques de la comparaison d'éléments biologiques. Sciences agricoles. Université Paris-Est, 2011. Français. ⟨NNT : 2011PEST1048⟩. ⟨pastel-00667797⟩



Record views


Files downloads