Le calcul de la distance d’inversion et celui d’une séquence optimale d’inversions pour transformer un génome dans um autre sont, des outils algorithmiques très utiles pour l’analyse de scénarios d’évolution réels. Quand les duplications de génes ne sont pas acceptées, il existe des algorithmes polynomiaux pour résoudre ces deux problèmes. Néanmoins, le nombre de séquences optimales différentes est très grand, et il faut alors considérer d’autres critères pour pouvoir réaliser une analyse plus précise. Une stratégie possible est celle de chercher les séquences qui respectent certaines contraintes biologiques, comme par exemple les intervalles communs, qui sont les ensembles de gènes co-localisés dans les génomes analysés - une séquence d’inversions qui ne sépare pas les intervalles communs doit être plus réaliste qu’une séquence qui sépare. Une autre approche est celle de générer l’univers de toutes les séquences optimales, mais, comme cet ensemble peut être trop grand pour être interpreté, un modèle pour regrouper des sous-ensembles de séquences optimales dans des classes d’équivalence a été proposé, ce qui permet de réduire la taille de l’ensemble à traiter. Néanmoins, le problème de trouver les classes sans énumérer toutes les solutions optimales restait ouvert. Un de nos résultats les plus importants est, donc, l’algorithme qui donne une réponse à ce problème, cest-à-dire, un algorithme qui génère une séquence optimale par classe d’équivalence et qui donne aussi le nombre de séquences par classe, sans énumérer toutes les spequences. Mais, bien que le nombre de classes soit beaucoup plus petit que le nombre de séquences, il peut être encore tropo grand. On propose alors l’utilisation de différentes contraintes biologiques, comme les intervalles communs (détectés initialement et progressivement), pour réduire le nombre de classes, et on montre comment utiliser ces méthodes pour analyser des cas réels d’evolution. En particulier, on analyse le scénario évolutif de la bactérie Rickettsia et des chromosomes sexuels X et Y chez l’être humain. Par rapport aux résultats des études précédentes, qui se sont basées sur une seule séquence optimale, on obtient une meilleure caractérisation de ces scénarios évolutifs. Tous les algorithmes développés sont implémentés en java, integrés à BAOBABLUNA, um logiciel qui contient des outils pour manipuler des génomes et des inversions. Le téléchargement et le tutoriel de BAOBABLUNA sont disponibles en ligne. Un autre résultat de notre travail est un modèle pour calculer une mesure de similarité entre deux génomes quand les duplications de gènes sont acceptées. On a montré que notre approche, qu’on appelle repetition-free longest common subsequence (RFLCS), est um problème NP-difficile, comme les autres approches qui considèrent aussi des gènes dupliqués pour calculer une distance génomique.
ABSTRACT - Calculating the reversal distance and finding one optimal sequence of reversals to transform a genome into another are useful algorithmic tools to analyse real evolutionary scenarios. When gene duplications are not allowed, there are polynomial algorithms to solve both problems. However, the number of different optimal sorcing sequences is usually huge and some additional criteria should be talten in consideration in order to obtain a more accurate analysis.One strategy is searching for sequences that respect some biological constraints, such as the common intervals, which are the list of clusters of co-localised genes between the considered genomes - an optimal sequence of reversals that does not brealt the common intervals may be more realistic than one that does break. Another approach is to explore the whole universe of sorting sequences, but, since this set may be too big to be directly interpreted, a model has been proposed to group the sorting sequences into classes of equivalence, reducing thus the size of the set to be handled. Nevertheless, the problem of finding an algorithm to direct generate the classes without enumerating all sequences was stated to be open. One of che most important results of our work is such an algorithm, and besides one representative, we are also able to give the number of sequences in each equivalence class. Although the number of classes is much smaller than the number of sorting sequences, it can also be too big. We then propose che use of different biological constr'aints, such as the common intervals (initially and progrwsively detected), to reduce the universe of sequences and classes, and show how to apply these methods to analyze real cases in evolution. In particular, we analyze the evolution of the Rickettesia bacterium, and of the sexual chromosomes X and Y in human. We obtain a better characterization of the evolutionary scenarios of these genomes, with respect to the results of previous studies, that were based on a single sorting sequence. All the algorithms developed in this work are implemented, integrated to BAQBLABLUNA a java framework to deal with genomes and reversals. Download and tutorial for BAQBABLUNA are available on-line.Another result of our work is a model to compute a measure of similarity between genomes when duplications are allowed. Our approach, that is called repetition-free longest common subsequence (RFLCS), was proven to lead to an NP-hard problem, as well as other approaches to compute a genomic distance measure considering gene duplications.
