|
Combinatoire et bio-informatique : comparaison de structures d'ARN et calcul de distances intergénomiques| old_uid | 736 |
|---|
| title | Combinatoire et bio-informatique : comparaison de structures d'ARN et calcul de distances intergénomiques |
|---|
| start_date | 2006/02/28 |
|---|
| schedule | 14h30 |
|---|
| online | no |
|---|
| summary | Nous présentons un ensemble de résultats concernant deux types de problèmes biologiques: (1) la comparaison de structures de molécules d'ARN et (2) le calcul de distances intergénomiques en présence de gènes dupliqués. Plus précisement, nous déterminons la complexité algorithmique de certains problèmes liés soit à la comparaison de structures de molécules d'ARN (distance d'édition, problème APS, recherche de motifs de 2-intervalles, design d'ARN), soit aux réarrangements génomiques (distances de breakpoints et d'intervalles conservés).
L'approche adoptée pour l'ensemble de ces problèmes a été de déterminer, si possible, des algorithmes exacts et rapides répondants aux problèmes posés. Pour tout problème pour lequel cela ne semblait pas possible, nous avons essayé de prouver qu'il ne peut être résolu de façon rapide. Pour ce faire, nous démontrons que le problème en question est algorithmiquement difficile (i.e. NP-complet). Enfin, le cas échéant, nous poursuivons l'étude de ce problème en proposant, essentiellement, trois types de résultats: (1) Approximation, (2) Complexité paramétrée, (3) Heuristique. Pour ce faire, nous utilisons des notions d'optimisation combinatoire, de mathématique, de théorie des graphes et d'algorithmique. |
|---|
| responsibles | Rispal, Clément |
|---|
| |
|