L’accroissement constant des capacités de séquençage de l’ADN entraîne l’émergence de nouveaux questionnements biologiques. Le stockage et le traitement de cette masse d’information restent des enjeux majeurs pour les années à venir. Durant le processus d’analyse des données génomiques, la recherche de séquences exactes ou proches, au travers de bases de données de génomes de références, est une tâche incontournable. Elle est notamment nécessaire dans les phases d’assemblage, d’alignement de séquences et plus généralement pour identifier la séquence de référence la plus proche d’une séquence requête. Ces tâches sont notamment essentielles dans le cadre d’étude en Biologie Évolutive, en Phylogénie ou en Métagénomique.

 

Traditionnellement, une grande majorité des techniques servant à réaliser ces différentes tâches, sont issues de méthodes en algorithmique du texte. L’objectif de cette thèse, est d’évaluer la possibilité d’utiliser des algorithmes issus du domaine de la comparaison des images numériques. En effet, les méthodes de production des images numériques ont connu une importante augmentation depuis ces 40 dernières années, entrainant des problèmes de recherche et de comparaison, qui par certains aspects, peuvent être considérées comme étant similaires aux traitements nécessaires à l’analyse des données génomiques.

 

Au cours de cette thèse, nous nous sommes plus particulièrement intéressés au concept de hachage perceptuel, utilisé habituellement pour indexer et comparer des images numériques, afin de déterminer si de telles méthodes sont pertinentes pour comparer des séquences exactes ou approchées au sein de base de données de séquences de références. Ainsi, nous proposons deux contributions. La première est une fonction de hachage perceptuel, permettant l’indexation de séquences ADN/ARN. Outre une diminution importante des données indexées par rapport aux séquences fournies en entrée, cette fonction de hachage a la particularité de conserver la propriété de comparabilité entre deux clés de hachages. Deux séquences ADN/ARN proches, auront des clés de hachage également proches et ainsi comparables. La seconde contribution, est l’adaptation d’une méthode permettant de faire ressortir les zones communes entre deux images, à la problématique de la comparaison de séquences ADN.

 

Ces travaux se placent dans un contexte d’accroissement des volumes de données génomique, où l’enjeu est de concevoir des algorithmes permettant d’identifier rapidement les génomes de référence les plus proches d’une séquence requête. Le but étant d’effectuer un prétraitement rapide, permettant de ne conserver que des séquences pertinentes et par la suite d’utiliser des méthodes plus classiques en bio-informatique.