Théorie des graphes et préliminaires mathématiques

En biologie, la génomique est une branche qui étudie les génomes. En particulier, elle s’intéresse à déchiffrer l’information qui est contenue au sein de la molécule d’acide désoxyribonucléique (ADN) qui est située dans les cellules des organismes vivants. Cette information est encodée à l’aide d’une séquence de nucléotides et prédétermine notamment certains caractères du vivant. La connaissance de cette séquence génomique est essentielle pour comprendre certains mécanismes biologiques. Elle est également utile pour beaucoup d’applications, on peut citer par exemple la médecine, la police scientifique ou la paléontologie. Pour l’obtenir, il est nécessaire de passer par un processus appelé séquençage. Il s’agit d’une technologie qui a émergé dans les années 1970 et qui n’a cessé d’évoluer jusqu’à aujourd’hui. Seulement, le séquençage nécessite de découper la molécule d’ADN en fragments, appelés lectures, avant d’obtenir l’ordre des nucléotides dans ceux-ci. On obtient donc après ce processus un ensemble de sous-séquences génomiques. Ces sous-séquences nécessitent d’être assemblées afin de pouvoir obtenir la séquence originelle complète. En général, on obtient cette séquence complète en passant par deux étapes : l’assemblage, où les lectures sont assemblées en séquences plus longues appelées contigs et l’échafaudage où les contigs sont échafaudés en séquences génomiques. La quantité de sous-séquences produites par le séquençage est telle que la reconstruction de la séquence complète nécessite l’utilisation de traitements automatisés, appelés algorithmes.

Les algorithmes sont des objets étudiés dans un champ disciplinaire appelé informatique fondamentale. Ils consistent en une suite d’instructions permettant la résolution de problèmes mathématiques. L’utilisation d’un algorithme pour la résolution d’un problème biologique nécessite au préalable de formuler ce problème sous la forme d’un modèle abstrait. La plupart du temps, on utilisera un outil appelé graphe, qui est constitué d’un ensemble de sommets et d’un ensemble d’arêtes qui relient ces sommets. Construire une telle modélisation permet de mettre à profit l’ensemble des connaissances accumulées par les mathématiciens en théorie des graphes et en informatique fondamentale pour résoudre le problème.

Une fois qu’un problème a été modélisé, il faut concevoir un algorithme pour pouvoir le résoudre. Il est facile de construire un algorithme pour la plupart des problèmes, mais il peut être en revanche très difficile d’en trouver un qui soit performant. La performance d’un algorithme s’évalue la plupart du temps par son temps d’exécution par rapport à la taille de l’objet sur lequel il travaille. Étant donné le volume très important de données à traiter pour les problèmes biologiques, l’idéal est un temps d’exécution polynomial par rapport à la taille de l’entrée. En effet, si le temps d’exécution d’un algorithme est exponentiel par rapport à la taille de l’entrée, alors il est illusoire d’espérer le dérouler sur des génomes de taille importante car il mettra trop de temps à donner une solution. Malheureusement, et c’est le cas pour de nombreux problèmes classiques, l’échafaudage ne peut probablement pas être résolu en temps polynomial. Il faut alors trouver des moyens pour produire malgré tout une solution, quitte à dégrader légèrement la qualité du génome produit.

Préliminaires sur la logique propositionnelle 

En logique propositionnelle, les objets de bases manipulés sont les propositions. Une proposition est un énoncé qui peut soit être vrai soit être faux. Dans le premier cas, une proposition prendra la valeur VRAI et dans le second cas, elle prendra la valeur FAUX. Par exemple, la proposition 3 < 5 est une proposition qui prend la valeur VRAI, à l’inverse la proposition « 3 est un nombre pair » qui prend la valeur FAUX. Une proposition qui dépend de paramètres est appelée prédicat. Ainsi, la proposition x = y est un prédicat qui dépend des valeurs de x et y. On peut construire une proposition à partir d’autres propositions en utilisant les opérations suivantes.

— Négation. Soit p une proposition, la négation de p, notée ¬p est la proposition dont la valeur est égale à VRAI si et seulement si la valeur p est égale à FAUX.

— Conjonction. Soient p1 et p2 deux propositions. La conjonction de p1 et p2, notée p1 ∧ p2 est la proposition dont la valeur est égale à VRAI si et seulement si les valeurs de p1 et p2 sont égales à VRAI. Dans le langage courant, on peut remplacer cet opérateur par « ET ».

— Disjonction. Soient p1 et p2 deux propositions. La disjonction de p1 et p2, notée p1 ∨ p2 est la proposition dont la valeur est égale à FAUX si et seulement si les valeurs de p1 et p2 sont égales à FAUX. Dans le langage courant, on peut remplacer cet opérateur par « OU ».

L’ordre de priorité des opérateurs est ¬, ∧ et ∨. Nous utiliserons des parenthèses quand cet ordre doit être modifié. Une proposition prenant la valeur VRAI est dite satisfaite et dans le cas contraire, elle est dite insatisfaite. Pour simplifier certaines opérations, nous introduisons également les opérateurs suivants.

— Implication. Soient p1 et p2 deux propositions. L’implication de p2 par p1, notée p1 ⇒ p2 correspond à la proposition ¬p1 ∨ p2.
— Double Implication. Soient p1 et p2 deux propositions. La double implication de p2 par p1, notée p1 ⇔ p2 correspond à la proposition (p1 ⇒ p2) ∧ (p2 ⇒ p1) .

Préliminaires sur les ensembles 

Un ensemble est une collection d’objets uniques, il peut être fini ou infini. La notation la plus communément admise pour décrire le contenu d’un ensemble utilise des accolades. Ces accolades peuvent entourer directement la liste des objets ou un prédicat caractérisant tous les objets de la collection. Par exemple, pour un ensemble E contenant les entiers 1, 2, 3, 4 et 5, on pourra écrire au choix {1, 2, 3, 4, 5}, {1, . . . , 5} ou {i | i ∈ N + ∧ i ≤ 5} (à comprendre : E contient tous les entiers naturels inférieurs ou égaux à 5). L’ensemble des entiers naturels est dénoté N et l’ensemble des naturels strictement positifs, utilisé dans l’exemple précédent, est dénoté N +. L’ensemble des nombres réels est noté R et l’ensemble des nombres réels strictement positifs est noté R +. Enfin, l’ensemble vide, c’est-à-dire l’ensemble ne contenant aucun élément, est dénoté ∅. La cardinalité d’un ensemble fini E, notée |E| est le nombre d’éléments que E contient .

Pour construire des propositions, on utilisera les notations suivantes. Pour indiquer qu’un objet x appartient à un ensemble E, on utilise le symbole ∈. Ainsi 1 ∈ E signifie que l’entier 1 appartient à l’ensemble E. Le symbole ∀ permet d’exprimer que tous les éléments x d’un ensemble E vérifient une propriété P(x), ce qui se notera ∀x ∈ E, P(x). Par exemple, la proposition ∀x ∈ {1, . . . , 5}, x ≤ 5 est satisfaite. Le symbole ∃, permet d’indiquer qu’il existe au moins un élément x de l’ensemble E qui vérifie une propriété P(x), ce qui se notera ∃x ∈ E, P(x). Ainsi, la proposition ∃x ∈ {1, . . . , 5}, x = 6 est insatisfaite. Les symboles ∀ et ∃ sont appelés des quantificateurs et peuvent être remplacés dans le langage courant par « pour tout » et « il existe », respectivement. Un ensemble E 0 est inclus dans un ensemble E si tous les éléments de E 0 appartiennent à E et on note cela E 0 ⊆ E. Autrement dit les deux propositions E 0 ⊆ E et ∀x ∈ E 0 , x ∈ E sont équivalentes. S’il existe au moins un élément de E qui n’appartient pas à E 0 , on parle alors d’inclusion stricte et on dénote cela par E 0 ⊂ E. Si E 0 est inclus dans E, strictement ou non, on dit que E 0 est un sous-ensemble de E.