Sujet : Développement d'outils conceptuels et algorithmiques pour l'analyse de structures biologiques arborescentes

Responsable : Pascal Ferraro et Serge Dulucq
Téléphone : 05 40 00 69 16
e-mail : ferraro@labri.fr
Site Web : http://www.labri.fr/~ferraro
Equipe : Combinatoire et algorithmique; Projet transversal AMBI

Présentation du sujet :

Dans l'optique de développer des méthodes de comparaison d'architecture de plantes, un premier travail de thèse (Ferraro, 2000) a été réalisé sur l'analyse d'un algorithme (Zhang, 96) permettant de comparer des structures arborescentes "non-ordonnées". Dans le meme temps une deuxième thèse (Tichit, 2003) a eu pour objectif le développement de nouvelles méthodes pour la modélisation et la comparaison de structures secondaires d'ARN (édition et alignement, approches globale et locale) modélisées sous la forme d'arborescences "ordonnées" (Zhang et Shasha, 1989). Ces premières explorations des techniques de comparaison d'arborescences ont ouverts un nombre important de voies de recherches algorithmiques et applicatives (Dulucq et Tichit, 2002, Ferraro et Godin, 2000,2003).

L'objectif de cette thèse est d'intégrer, à partir de ces études préliminaires, les différents travaux dédiés à l'édition d'arborescence, afin de proposer un point de vue unifié des différentes techniques. D'un point de vue applicatif, les biologistes, à l'heure actuelle, ne disposent d'aucun outil logiciel l'analyse d'arborescences, alors qu'ils utilisent fréquemment des logiciels comme Blast ou Fasta dédiés à la comparaison de séquences. Dans ce cadre, cette thèse aura pour but de développer un outil conceptuel et informatique pour la comparaison d'objets biologiques arborescents.

Références :
(Dulucq et Tichit 2003) S. Dulucq et L. Tichit, RNA secondary structure comparison: exact analysis of the Zhang-Shasha tree edit algorithm. Theor. Comput. Sci. 306(1-3): 471-484 (2003)

(Ferraro et Godin 2000a) P. Ferraro et C. Godin, A distance measure between plants architectures, Annals of Forest Sciences (2000) 57:445-461

(Ferraro et Godin 2002a) P. Ferraro et C. Godin, An algorithm for comparing quotiented tree graphs. Algorithmica (2003) 36: 1-39

(Ferraro et Godin 2002b) P. Ferraro et C. Godin, Optimal mappings with minimum number of connected components in tree-to-tree comparison problems. Accepté pour publication à Journal of Algorithms [Jan 2003], Ref : YJAGM 1304, 283

(Tichit, 2003) L. Tichit, Algorithmique des structures biologiques : l'édition d'arborescences pour la comparaison des structures secondaires d'ARNs. thèse de l'université de Bordeaux1. 2003.

(Zhang et Shasha 1989) Kaizhong Zhang et Dennis Shasha, Simple Fast Algorithms for the Editing Distance Between Trees and Related Problems. SIAM J. Comput. 18(6): 1245-1262 (1989)

(Zhang, 1996) K. Zhang. A constrained edit distance between unordered labeled trees. Algorithmica, 15:205–222, 1996.

Commentaires :
Certaines Publications sont disponibles à l'adresse : http://www.labri.fr/~ferraro/biblio_perso.html