La comparaison de séquences d'ADN : des fondements de la bioinformatique aux nouveaux défis posés par les séquenceurs de nouvelle génération

La comparaison de séquences d'ADN est au coeur de nombreuses applications en biologie : pour détecter des gènes dans les génomes, identifier des mutations responsables de maladies ou encore reconstruire les relations de parenté entre espèces. C'est aussi un des problèmes fondateurs de cette discipline récente qu'est la bioinformatique. Dès les premiers séquençages de séquences d'ADN dans les années 70, des mathématiciens et informaticiens se sont emparés de ce problème. Je présenterai tout d'abord le problème d'alignement de séquences et les algorithmes basés sur le principe de programmation dynamique qui permettent de le résoudre de manière exacte. Puis j'exposerai les principales heuristiques qui ont été développées pour accélérer les temps de calculs. Enfin, avec l'apparition de nouvelles techniques de séquençage ces dernières années et le déluge de séquences que connait actuellement la biologie, il a fallu repenser complètement ces algorithmes pour passer à l'échelle en termes de temps de calcul et de mémoire utilisée. J'illustrerai ces nouveaux défis par une méthode que nous avons développée afin de comparer la diversité biologique de milliers d'échantillons d'eau de mer prélevés tout autour du globe (expédition Tara Océan).