:: Enseignements :: Master :: M2 :: 2007-2008 :: Stages ::
[LOGO]

Prise en compte de Contraintes Structurelles dans la Comparaison de Séquences d'ARN : le problème LAPCCS

Ce stage concerne le domaine de l'Algorithmique au sein de la thématique AlgoB de l'IGM et ComBi du LINA.

Lieu du stage

Selon la provenance de l'étudiant, le stage est a effectuer au sein : Plus précisément: un étudiant provenant du Master Recherche de Nantes fera son stage au LINA, un étudiant provenant du Master Recherche de Marne-la-Vallée fera son stage à l'IGM, et un étudiant d'une autre provenance choisira le lieu de stage de son choix, entre Nantes et Marne-la-Vallée.

Encadrement

Présentation générale du domaine

Le stage proposé s'inscrit dans le domaine de l'algorithmique en bio-informatique. Le but est d'étudier la "faisabilité" algo- rithmique de certains problèmes issus de la biologie, avant de proposer, d'implémenter et de tester des algorithmes rapides et efficaces. Le type de problème étudié dans ce stage est l'extraction de motifs contraints dans les ARN.

Présentation et objectifs du stage

L'ARN et sa représentation sous forme de structure arc-annotée. L'ARN est un acide nucléique composé de quatre bases : A, U , C et G. Il peut donc être vu comme un mot (càd, une suite ordonnée) sur cet alphabet. Cependant, l'ARN est une molécule dite "simple brin", obtenue par repliement sur elle-même à la faveur d'appariements entre paires de nucléotides (A − U ou G − C). Donc, l'ARN ne peut être réduite à sa séquence : l'information donnée par son repliement doit être prise en compte. On parle alors de structure d'ARN. Dans ce cas, la modélisation est la suivante : l'ARN est représenté sous la forme d'une séquence arc-annotée (S1,P1), qui se compose:

Le Problème LAPCCS. Dans ce projet, on s'intéresse au problème LAPCCS. Avant de le définir, nous présentons d'abord le problème LAPCS (pour "Longest Arc-Preserving Common Subsequence") : étant donné deux structures (S1,P1) et (S2,P2), ce problème consiste à trouver une sous-structure (S,P) arc-préservante commune à (S1,P1) et (S2,P2), et dont la longueur (en terme de bases) soit maximale. Le terme arc-préservant signifie qu'il existe un arc entre deux bases dans (S,P) si et seulement si il existe un arc entre leurs bases correspondantes dans (S1,P1) et dans (S2,P2).

Exemple 1 : Soit (S1,P1) et (S2,P2) deux séquences tq: 
 
P1 : (.....) 
S1 : AGGCGCU
S2 : ACGGCCU 
P2 : (.....)
Alors le LAPCS pour ces deux structures est (S3 , P3 ) et sa longueur est donc égale à 6. 
 
P3 : (....) 
S3 : AGGCCU

Le problème auquel on s'intéresse est le problème LAPCCS (pour "Longest Arc-Preserving Common Constrained Subsequence"). En entrée du problème, on a maintenant trois structures (S1,P1), (S2,P2) et (Sh,Ph), et le but est de rechercher la plus longue sous-structure arc-préservante (S,P), sous la contrainte que (S,P) contienne elle-même (Sh,Ph) comme sous-structure arc-préservante.

Exemple 2 : Soit (S1,P1) et (S2,P2), (Sh,Ph) tq 
 
P1 : (.....) 
S1 : AGGCGCU
				
Ph : (..) 
Sh : ACGU

S2 : ACGGCCU 
P2 : (.....)
Alors le LAPCCS pour ces trois structures est (S,P), et sa longueur est donc égale à 5. 
 
Ph : (...) 
Sh : ACGCU
Ce problème a déjà été étudié dans le cas des séquences, ce qui peut être vu comme le cas (extrême) où aucune structure ne possède d'arcs (donc P1 = P2 = Ph = {}) [2,3,4]. Cependant, dans le cas des structures, aucun résultat n'existe.

Travail demandé

Le travail commencera par un étude des articles cités, lesquels ne nécessitent pas de connaissances préalables spécifiques en biologie ; cependant, un goût prononcé pour l'algorithmique sera indéniablement un avantage.
Le problème sera ensuite abordé sous l'angle de la complexité algorithmique. En effet, les données d'entrée (les séquences arc-annotées) peuvent être classifiées en fonction de "l'organisation" des arcs (par exemple, les structures n'ayant pas d'arcs qui se croisent appartiennent à une classe spécifique – mais il en existe bien d'autres...). On va donc chercher à déterminer la com- plexité du problème LAP CCS en fonction des classes auxquelles appartiennent (S1,P1), (S2,P2) et (Sh,Ph), ce qui donne un grand nombre de cas possibles.
Pour chacun de ces cas, on cherchera donc à déterminer dans quelle classe de complexité se situe le problème :
  • s'il est polynomial, on proposera un algorithme performant pour le résoudre
  • s'il est NP-complet, après l'avoir prouvé, on tentera de contourner la difficulté, essentiellement dans deux directions :
    • en fournissant des algorithmes approchés (pour lesquels on peut quantifier l'écart entre la solution fournie et la solution optimale) ;
    • en fournissant des algorithmes dits de "Fixed-Parameter Tractability", c'est-à-dire des algorithmes exponentiels, mais dont on sait que le paramètre à l'exposant reste petit dans la pratique.
On fournira, le cas échéant, des algorithmes, qui seront implémentés et testés sur des données réelles.

Bibliographie

  1. P.A. Evans. Algorithms and Complexity for Annotated Sequence Analysis. PhD thesis, University of Victoria, 1999.
  2. Chin, F. Y., De Santis, A., Ferrara, A. L., Ho, N. L., and Kim, S. K. 2004. A simple algorithm for the constrained se- quence problems. Inf. Process. Lett. 90, 4 (May. 2004), 175-179.
  3. Zeshan Peng. Structure Comparisons in Bioinformatics. PhD thesis, The University of Hong Kong, January 2006.
  4. Yin-Te Tsai : The constrained longest common subsequence problem. Inf. Process. Lett. 88(4) : 173-176 (2003).
  5. G. Blin. Combinatoire and Bio-informatique : Comparaison de structures d'ARN et calcul de distances intergénomiques. PhD thesis, Université de Nantes, 2005.
© Université de Marne-la-Vallée