Dans cette présentation à plusieurs voix, nous montrerons comment des questions liées à l’évolution du style littéraire chez certains auteurs ou certaines autrices du XIXe siècle a motivé la recherche de l’ordre optimal sur les feuilles d’un arbre, pour correspondre au mieux à un ordre fourni en entrée. Cette question correspond à deux problèmes précédemment introduits en bioinformatique dans le contexte de la comparaison d’arbres phylogénétiques, OTCM et OTDE. Le premier consiste à trouver un ordre qui minimise le nombre d’inversions avec l’ordre en entrée sur les feuilles alors que le second consiste à supprimer le nombre minimal de feuilles de l’arbre pour le rendre cohérent, sur les feuilles restantes, avec l’ordre en entrée. Nous montrons que ces deux problèmes sont NP-complets dans le cas général. Nous fournissons un algorithme en temps polynomial pour le second problème dans le cas où le degré maximal est borné dans l’arbre, et un algorithme de complexité paramétrée par un paramètre borné par le nombre de feuilles à supprimer. Nous explorons les possibilités de mise en œuvre pratique de ces algorithmes sur des arbres obtenus par classification hiérarchique de corpus de romans du XIXe siècle. Nous présentons aussi une approche directe pour étudier l’évolution de l’idiolecte de romanciers et romancières du XIXe siècle.
Reordering a tree according to an order on its leaves and studying the evolution of the idiolect of writers
In this multi-voice presentation, we will show how questions related to the evolution of literary style among several authors of the 19th century motivated the search for the optimal order on the leaves of a tree to best correspond to an order provided as input. This question corresponds to two problems previously introduced in bioinformatics in the context of phylogenetic tree comparison, OTCM and OTDE. The first problem consists in finding an order which minimizes the number of inversions with an input order on the leaves, while the second one consists in removing the minimum number of leaves from the tree to make it consistent with the input order on the remaining leaves. We show that both problems are NP-complete when the maximum degree is not bounded. We provide a polynomial-time algorithm for OTDE in the case where the maximum degree is bounded by a constant and an FPT algorithm in a parameter lower than the number of leaves to delete. We explore the possibilities of practical use of those algorithms on trees obtained by clustering French novels of the 19th century. We also present a more direct approach to study the evolution of the idiolect of French 19th century writers.
Localisation
Salle de séminaire 4B125 (bâtiment Copernic)
5 Boulevard Descartes 77420 Champs-sur-Marne