Résumé Nous présentons dans ce mémoire une nouvelle approche permettant de créer et d'exploiter des graphes de recombinaison ancestraux comportant un grand nombre de marqueurs génétiques. Nous utilisons principalement une représentation binaire ainsi que des fonctions booléennes applicables sur des séquences de marqueurs afin d'implémenter un logiciel fait sur mesure pour accomplir cette tâche de manière efficiente. De plus, nous détaillons une heuristique de construction bien connue et nous proposerons un algorithme novateur minimisant le nombre de recombinaisons requises pour parvenir à un ancêtre commun. Enfin, nous exposons quelques résultats sur l'effcacité de notre approche.
Mots-clés : graphe de recombinaison ancestral, cartographie génétique, processus de coalescence, heuristiques, mutation.

Introduction

Depuis 1859, lors de la publication du célèbre ouvrage de Charles Darwin sur l'origine des espèces (Darwin, 1859), l'Homme a toujours rêvé de connaitre l'histoire complète de la vie. Le concept d'arbre de la vie au sens biologique a ainsi vu le jour. Cette théorie stipule que chacun d'entre nous possède un ancêtre commun avec tout autre organisme vivant sur la planète. Cette idée constitue une des plus grandes percées scientifiques accomplies par l'esprit humain. Puisque certains de nos prédécesseurs sont morts depuis maintenant plus de 4 milliards d'années, nous ne pourrons probablement jamais savoir exactement comment la vie a évolué, ni même de quelle manière elle est apparue. Mais qui reste indifférent à l'idée de pouvoir observer l'ancêtre commun que nous partageons avec cet arbre que nous avons escaladé lorsque nous étions enfant? Beaucoup de temps s'est écoulé depuis Darwin et la découverte de l'acide désoxyribonucléique, ou ADN. Nos connaissances continuent sans cesse de s'affiner et de confirmer sans aucun doute la théorie de l'évolution de Darwin. Aujourd'hui, ces notions sont mises à contribution pour peauffner notre reconstitution de l'évolution de la vie. De façon plus générale, la phylogénie étudie les liens évolutifs entre les êtres vivants. Le niveau généalogique s'intéresse surtout à l'étude entre individus dans une population. Le niveau interspécifique quant à lui, explore les liens entre des espèces différentes et rend une analyse plus globale. Ces liens peuvent être intuitivement représentés au moyen d'un graphe au sens mathématique. Ce graphe prend souvent la forme d'un arbre, car il est plus facile de comprendre les relations de parenté pour un ensemble d'organismes donnés sous cette représentation. Un arbre généalogique est un exemple simpliste d'une phylogénie. Lors de la genèse de cette science, les arbres étaient surtout basés sur des observations qualitatives, comme la variation de la forme du bec de plusieurs espèces d'oiseaux par exemple. Le degré de certitude des inférences était alors relativement faible. La découverte et le séquençage de l'ADN en revanche ont permis d'augmenter énormément la qualité de ces arbres. La performance et le coût des séquenceurs s'étant grandement améliorés, la quantité d'informations génétiques disponibles dans les diverses banques de données a explosé depuis quelques années. Actuellement, on peut facilement obtenir les données nécessaires pour effectuer de l'inférence phylogénétique. Ces phylogénies sont très utiles dans plusieurs domaines et ont parfois des applications concrètes. Dans les chapitres qui suivent, nous nous penchons surtout sur deux sortes particulières de graphes phylogénétiques, soit le graphe de recombinaison ancestral qui s'appuie sur le processus de coalescence lors de son inférence ainsi qu'un arbre phylogénétique interespèce. Plus spéciquement, nous nous intéressons à la manière de générer ces graphes rapidement sur un grand nombre de marqueurs génétiques ainsi que certaines méthodes pour extraire un maximum d'information statistique. Avant de nous engager plus en profondeur dans le graphe de recombinaison ancestral, nous introduisons certains concepts génétiques importants dans les deux chapitres suivants. Puis, nous détaillons les particularités des graphes de recombinaison ancestraux (ARGs) lors du troisième et du quatrième chapitre. Le chapitre cinq sera consacré aux différents algorithmes et méthodes statistiques appliquées aux ARGs. Enfin, nous concluons avec les résultats obtenus avec notre nouvelle approche.

Conclusion

Le problème que nous avons exploré lors de notre recherche, soit la génération efficiente de graphes de recombinaison ancestraux, se situe au carrefour de trois domaines principaux. Premièrement la biologie, où la problématique prend racine. Puis, plusieurs branches des mathématiques telles que la statistique et l'algèbre nous fournissent la plupart des outils essentiels pour modéliser et analyser la quantité sans cesse croissante de données biologiques dont nous disposons. Enfin, comme la qualité des résultats obtenus à l'aide des graphes est directement proportionnelle à la quantité de données que les algorithmes sont aptes à traiter, une implémentation informatique de qualité est de mise. Plusieurs aspects de l'informatique tant théoriques que pratiques permettent d'optimiser le traitement des données pour que nous soyons en mesure d'obtenir des temps d'exécution raisonnables. L'implémentation de FastARG est donc le fruit de multiples résultats provenant de ces trois domaines. Bien que nos tentatives de parallélisation n'aient pas été fructueuses, les opérations séquentielles semblent avoir des performances prometteuses. Toutefois, l'ensemble des métadonnées produites par FastARG représente un avantage majeur pour le calcul de statistiques découlant de ces graphes. Nous sommes donc persuadés que FastARG ouvre une nouvelle approche computationnelle pour la génération de graphes de recombinaison ancestraux comportant un grand nombre de marqueurs génétiques. Ce travail peut donc avoir des implications intéressantes en cartographie génétique, car les ARGs sont un des outils principaux permettant d'inférer la position des gènes.