Analyse de séquences génétiques par compression : localisation optimale de régularités et comparaison d'une séquence relativement à d'autres

La compression informatique peut être utilisée efficacement pour analyser de l'information, plus particulièrement des séquences de symboles. En effet, un programme de compression parvient à réduire la taille d'une séquence s'il parvient à exploiter des redondances (des ``régularités'') dans la séquence. Suivant le principe MDL (Minimum Description Length), on tente d'approcher la description la plus courte d'une séquence pour en trouver une ``explication probable''.

Deux applications de l'approche MDL pour l'analyse de séquences génétiques seront présenteés.

La première application concerne la localisation optimale de régularités dans une séquence.
Habituellement, les méthodes de compression exploitent les redondances d'un bout à l'autre de la séquence à comprimer. Si certaines zones sont effectivement raccourcies de cette façon, d'autres zones sont malheureusement rallongées. Nous proposons un algorithme permettant, une fois une séquence comprimée, de rompre le schéma de compression là où il n'est pas intéressant en recopiant ces morceaux de la séquence tels quels. Le gain global en compression s'en trouve amélioré. Notre algorithme propose une décomposition, en zones à comprimer et zones à recopier, optimale dans le sens où elle maximise le gain en compression
résultant. Notre algorithme d'optimisation fonctionne en temps O(n log n) où n est la longueur de la séquence. L'optimisation nous permet donc de localiser, de manière optimale, les zones régulières et irrégulières pour le type précis de régularités exploité par la méthode de compression initiale. Cet algorithme a été utilisé en pratique pour localiser des répétitions en tandem approximatives dans les séquences d'ADN.

La seconde application concerne la localisation de fragments d'une séquence test que l'on retrouve dispersés dans un ensemble d'autres séquences appelées séquences dictionnaires. Pour cela, notre algorithme tente de comprimer la séquence test relativement à l'ensemble des séquences dictionnaires, c'est-à-dire qu 'il tente de décrire la séquence test comme une succession de fragments issus des séquences dictionnaires ou de fragments complètement indépendants des dictionnaires. Les efforts portent sur la minimisation de longueur la description ainsi obtenue. Le problème est modélisé comme la recherche d'un plus court chemin dans un graphe orienté. Cette nouvelle approche
pourrait être appliquée par exemple dans le domaine de la phylogénie...