Contexte Scientifique
Thèmes abordés

Depuis quelques années, le domaine de l'informatique appliquée à la biologie se structure et se complexifie. Deux phénomènes importants sont à l'origine de cette évolution. En premier lieu, l'amélioration et l'automatisation des outils biologiques d'investigation, comme le séquençage à grande échelle et les données d'expressions, permettent d'obtenir des données plus fines et en plus grandes quantitées. Ensuite, l'amélioration de la compréhension mutuelle des mondes informatiques et biologiques permet de proposer des modèles informatiques plus complexes, mais adaptés aux besoins de la biologie.

Pour se convaincre de cette évolution rapide, il suffit de regarder le nombre de modèles informatiques proposés actuellement en bio-informatique qui manipulent, non plus des séquences seules (comparaison, alignement) comme c'était le cas peu de temps auparavant, mais des graphes compliqués batis sur ces séquences ou sur d'autres données, bi-dimensionnelles ou tri-dimensionnelles.

Un exemple typique en est le clustering à grande échelle de séquences. Dans un scénario maintenant classique, un ensemble de séquences de protéines sont comparées deux à deux au moyen d'un algorithme de comparaison de séquences. Chaque comparaison donne un score. Le graphe des scores est ensuite étudié pour regrouper les protéines par familles ayant les mêmes propriétés. Il faut bien noter que ces graphes sont de plus en plus gigantesques. Le récent projet TERAPROT a bénéficié des ordinateurs du CEA-DAM (construit pour la simulation des essais nucléaires) pendant une semaine pour obtenir ce graphe sur un ensemble de 250 000 protéines, obtenant un graphe avec 625×10⁸ arÍtes !  Les problèmes algorithmiques sur les grands graphes apparaissent de suite. Comment gérer ce type de graphes ? Comment proposer des algorithmes de clustering efficaces en complexité linéaire ou à l'extrème limite quadratique sur ces graphes ? Comment comparer les graphes obtenus par des comparaison de séquences différentes ? de plus, ces graphes devraient pouvoir évoluer. En effet, les séquences de protéines sont souvent affinées après une production première. Comment rendre ces graphes et algorithmes dynamiques pour effectuer des modifications locales sans tout reconstuire ?

Un autre exemple est la modélisation de réseaux de gènes et de régulations, ou encore de voies métaboliques. Dans les réseaux de gènes et les réseaux de régulation, les gènes intéragissent entre eux en agissant en inibant ou augmentant l'action d'autres gènes.  Dans le cas des voies métaboliques, des protèines agissent entre elles et l'ensemble des intéractions est représenté par des graphes particuliers ou chaque état représente une réaction chimique repertoriée. La base KEGG répertorie de plus en plus de voies métaboliques. Les problémes algorithmiques sur les graphes posés dans ces deux cas sont complexes. Comment prédire l'évolution dynamique de ces graphes en fonctions des propriétés des sommets (représentant des génes ou des protéines) ? Comment comparer/compléter des réseaux en comparant les génomes entre eux ?

Ainsi, dans le domaine de la biologie moléculaire post-génomique, il est assez naturel de construire des graphes sur des séquences et de les étudier, ou encore d'étudier des paires d'intervalles sur des séquences et les graphes d'intersection associés.

En outre, si la biologie moléculaire pose de plus en plus de problémes algorithmiques difficiles sur les graphes, d'autre domaines de la biologie, plus traditionnels, suivent cette évolution. Par exemple, la modélisation informatique du développement des plantes utilise maintenant des arboresences multi-échelles qui posent de profond problémes algorithmiques sur ces graphes particuliers.

D'une maniére générale, de nouveaux besoins en modélisation et algorithmique sur des modéles liés aux graphes apparaissent dans de nombreux domaines de la biologie, mais ces modéles ne sont pas encore complétement figés. Dans de nombreux cas, la modélisation de ces problémes par les graphes fait entrer en jeu des familles de graphes trés connues (graphes d'intervalles, graphes de comparabilité, graphes triangulés ou faiblement triangulés, etc). Il est alors souvent possible d'en déduire des algorithmes polynomiaux répondant aux problémes posés, en s'appuyant sur la littérature trés fournie dans le domaine. Il reste cependant des problémes pour lesquels les graphes associés ne font pas nécessairement partie de familles connues. Néanmoins, ces graphes restent souvent trés spécifiques, et une étude plus approfondie est alors nécessaire. Il s'agit donc d'étudier des problémes dans lesquels la modéisation à base de graphes n'est pas triviale et l'algorithmique associée intéressante.

La modélisation de problèmes de clustering d'objets biologiques en termes de graphes n'est pas nouvelle puisque par exemple dans le domaine de la reconstruction phylogénétique on peut citer des travaux des années 70. Toutefois, les progrès des biotechnologies de ces dernières décennies ont grandement augmenté à la fois la quantité de données disponibles et les types de données  utilisées.

L'augmentation de la quantité de données entraine la recherche d'algorithmes toujours plus efficaces en temps calcul. La réduction de complexité des algorithmes de clustering basés sur les graphes s'obtient la plupart du temps par des algorithmes non-triviaux sur les graphes dynamiques (au fur et à mesure que les clusters principaux sont établis, la structure du graphe se modifie).

Le développement de nouveaux types de données (par exemple données d'expression), amène à concevoir des approches de clustering adaptées. De nouveaux problèmes, comme celui des superarbres surgissent aussi du fait de l'accumulation de données de différents types.

Dans tous les cas, trouver la modélisation en terme de graphes la plus pertinente biologiquement est souvent un problème non-trivial comme en atteste plusieurs révisions des modélisations proposées.

On cherche également à déterminer la complexité algorithmique de problèmes tels que la reconstruction des phylogénies à partir de matrices de distance, le pattern matching des 2-intervalles modélisant des structures secondaires d'ARN, ou les SNPs (Single Nucleotid Polymorphism).

Les paires d'intervalles sont des objets particulièrement bien adaptées à l'étude des structures secondaires d'ARN. En effet, les différentes relations de comparaison (précédence, englobement et inclusion) qui existent entre deux paires d'intervalles disjoints définissent naturellement des classes de motifs représentant différentes classes de structures secondaires d'ARN. Ces problèmes se modélisent très simplement sous forme de problèmes combinatoires sur les graphes d'intersection associés. Bien que ces problèmes soient très difficiles dans le cas général, il a pu Ítre établi que le cas particulier des structures secondaires d'ARN sans pseudo-noeuds est résoluble en temps polynomial. Cependant, ce dernier cas - le plus important au sens biologique - souffre encore d'une complexité en pire cas trop élevée. Il est important de souligner que la modélisation des structures secondaires par graphes est un domaine de recherche très actifs actuellement: D. Goldman, S. Istrail et C.H. Papadimitriou ont proposé un modèle plus simple pour l'étude des similarités des protéines, P. Evans dans un premier temps puis J. Gramm, J. Guo et R. Niedermeier ensuite ont utilisé des modélisations basées sur les graphes pour l'étude des sous-séquences communes avec annotations.

Les puces à ADN permettent aujourd'hui de mesurer et de visualiser très rapidement les différences d'expression entre les gènes et ceci à l'échelle d'un génome complet. L'hypothèse communément admise par les biologistes est que les gènes dont les profils d'expression sont similaires sont susceptibles d'Ítre impliqués dans un mÍme processus biologique. Il est assez naturel d'associer à un ensemble de puces à ADN un graphe de similarité: chaque sommet représente un gène et chaque arÍte reflète la similarité entre deux gènes. Il est extrÍmement difficile de manipuler de tels graphes: le génome de
Saccharomyces cerevisae comporte plus de 6000 gènes tandis que celui de mus musculus est estime a environ 30000 gènes. Il est essentiel de proposer des algorithmes linéaires ou quadratique dans le pire cas. Puisque la plupart des gènes ne sont pas impliqués dans une expérience donnée, un clustering complet de ces graphes n'est pas toujours la meilleure solution et les biologistes ont besoins d'algorithmes rapides permettant d'extraire uniquement des sous-graphes de forte connexité pertinents (c'est-à-dire satisfaisant un ensembles de contraintes énoncées par les biologistes). De plus, la publication croissante de séquences de nouveaux organismes permet aujourd'hui d'étudier plus avant les comparaisons entre espèces au niveau du
transcriptome. En utilisant des tables d'orthologie entre espèces (par exemple entre Saccharomyces cerevisae et Scizosaccharomyces pombe), ces problèmes se modélisent par des problèmes de recherche de sous-graphes communs. Cependant, la taille des graphes considérés empêchent l'utilisation de méthodes exhaustives et de nouveaux algorithmes (exacts ou d'approximation) efficaces en temps doivent donc être proposés.

Est-il possible de simplifier le modèle d'arborescence multi-échelle pour modéliser la croissance des plantes (introduire la dynamique) ne généralisation à des classes particulières de graphes multi-échelles sera étudiée (treillis, graphes sans circuit...)

Une fois les modèles spécifiés nous étudierons leur algorithmique (i.e. comment répondre efficacement aux questions soulevées dans les applications biologiques.

Quelles sont les modélisations utiles pour tenir compte de la dynamique des problèmes biologiques que l'on cherche à modéliser ?