Reconstruction des ancêtres de séquences partageant leur histoire duplicative

La reconstruction de l'histoire duplicative d'une séquence génomique est un problème où on tente d'expliquer l'évolution d'un segment avec des mutations ponctuelles et des duplications. Une heuristique intéressante est la réduction récursive de la duplication la plus récente : à chaque étape, on identifie la duplication la plus récente, on la réduit et on recommence sur la séquence résultante. L'identification des segments issus de la duplication la plus récente peut se faire avec une mesure de coûts sur cette paire de segments, comme la distance de Hamming par exemple. Lorsque des séquences partagent leur histoire duplicative, il est possible d'élaborer des mesures de distance qui traitent l'ensemble des segments issus de la duplication la plus récente de ces séquences en parallèle. On voit, dans ce mémoire, des algorithmes basés sur les travaux de Fitch (1971), Sankoff (1975), Benson et Dong (1999) et Belcaid et al. (2011). Ces algorithmes mesurent le coût moyen des mutations pré-spéciation des segments issus de la duplication la plus récente. Nous développons ces algorithmes pour permettre le traitement de plusieurs séquences en parallèle et présentons diverses optimisations.\ud ______________________________________________________________________________ \ud MOTS-CLÉS DE L’AUTEUR : Bioinformatique, répétitions en tandem approximatives, duplications en tandem, reconstruction parcimonieuse de l'histoire duplicative, partage d'histoire duplicative