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)
Complete list of metadatas

Cited literature [177 references]  Display  Hide  Download

https://pastel.archives-ouvertes.fr/pastel-00667797
Contributor : Abes Star <>
Submitted on : Wednesday, February 8, 2012 - 1:29:22 PM
Last modification on : Wednesday, April 11, 2018 - 12:12:03 PM
Long-term archiving on : Wednesday, May 9, 2012 - 2:35:16 AM

File

TH2011PEST1048_complete.pdf
Version validated by the jury (STAR)

Identifiers

  • HAL Id : pastel-00667797, version 1

Citation

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

Share

Metrics

Record views

700

Files downloads

671