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

Résumé : Pour mieux saisir les liens complexes entre génotype et phénotype, une méthode utilisée consiste à étudier les relations entre différents éléments biologiques (entre les protéines, entre les métabolites...). Celles-ci forment ce qui est appelé un réseau biologique, que l'on représente algorithmiquement par un graphe. Nous nous intéressons principalement dans cette thèse au problème de la recherche d'un motif (multi-ensemble de couleurs) dans un graphe coloré, représentant un réseau biologique. De tels motifs correspondent généralement à un ensemble d'éléments conservés au cours de l'évolution et participant à une même fonction biologique. Nous continuons l'étude algorithmique de ce problème et de ses variantes (qui admettent plus de souplesse biologique), en distinguant les instances difficiles algorithmiquement et en étudiant différentes possibilités pour contourner cette difficulté (complexité paramétrée, réduction d'instance, approximation...). Nous proposons également un greffon intégré au logiciel Cytoscape pour résoudre efficacement ce problème, que nous testons sur des données réelles.Nous nous intéressons également à différents problèmes de génomique comparative. La démarche scientifique adoptée reste la même: depuis une formalisation d'un problème biologique, déterminer ses instances difficiles algorithmiquement et proposer des solutions pour contourner cette difficulté (ou prouver que de telles solutions sont impossibles à trouver sous des hypothèses fortes)
Type de document :
Thèse
Autre [cs.OH]. Université Paris-Est, 2011. Français. <NNT : 2011PEST1048>
Liste complète des métadonnées


https://pastel.archives-ouvertes.fr/pastel-00667797
Contributeur : Abes Star <>
Soumis le : mercredi 8 février 2012 - 13:29:22
Dernière modification le : jeudi 22 juin 2017 - 14:12:54
Document(s) archivé(s) le : mercredi 9 mai 2012 - 02:35:16

Fichier

TH2011PEST1048_complete.pdf
Version validée par le jury (STAR)

Identifiants

  • 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>

Partager

Métriques

Consultations de
la notice

481

Téléchargements du document

434