Développement d'outils conceptuels et algorithmiques pour l'analyse de structures biologiques arborescentes
Institution:
Bordeaux 1Disciplines:
Directors:
Abstract EN:
Trees are an important data structure in several fields: botanic, molecular biology, etc. Particularly, in most botanical applications, trees are used to represent the topological structure of plants architecture. The concept of architecture plays an important role in the understanding of the development and the growth of plants. Thus, the comparison of plant architectures has many applications in various fields of botany as agronomy, horticulture, arboriculture or sylviculture. Some initial works aimed at exploring tree comparison algorithms, their applications in botany and their extensions. The algorithms studied here are based on the generalization of the methods for computing similarity between sequences. Their general principle consists in building a target tree by applying various structural operations, called edit operations, to an initial tree. In this thesis, we propose a unification of the various tree edit methods by introducing the class of semi-ordered trees which envolves unordered and ordered trees. Furthermore, we introduce new extensions of edit algorithms by modifying the constraints dedicated to the comparison of plant architectures or RNA secondary structures. For instance, multi-scales aspects, semi-order or order relations between the entities of the structures are now taken into account.
Abstract FR:
Les arborescences sont des structures de données fréquentes en biologie : botanique, biologie moléculaire, etc. En particulier, dans certaines applications botaniques, les arborescences sont utilisées pour représenter la structure topologique de l'architecture d'une plante. La notion d'architecture joue un rôle important dans la compréhension des modalités d'élaboration et de croissance des plantes. Ainsi la comparaison de l'architecture des plantes a des applications potentielles importantes dans divers domaines de la biologie végétale comme l'agronomie, l'arboriculture, l'horticulture ou encore la sylviculture. Des travaux initiaux ont eu pour objectif d'explorer les algorithmes de comparaison d'arborescences, d'en étudier les applications dans le domaine de la biologie végétale et d'envisager différentes extensions. La famille d'algorithmes étudiée s'appuie sur la généralisation des méthodes de calcul de distance entre séquences. Leur principe général consiste à reconstruire une arborescence cible en appliquant à une arborescence initiale différentes opérations structurelles, appelées opérations d'édition. Dans cette thèse, nous proposons d'une part une unification des méthodes d'édition d'arborescences en introduisant la classe des arborescences semi-ordonnées qui englobe les arborescences non-ordonnées et ordonnées. D'autre part, nous proposons de nouvelles extensions des algorithmes d'édition en modifiant les contraintes dédiées à la comparaison d'architectures de plantes ou de structures secondaires d'ARN comme la prise en compte des aspects multi-échelles, de semi-ordre ou d'ordre dans les structures.