AlgoB :: Algorithmics for Bioinformatics

Research > Projects

Professional training

LAPCCS

Lieu du stage
Le stage est a effectuer au sein du Laboratoire d'Informatique de l'Institut Gaspard Monge qui se situe à
l'Université Paris-Est Marne-la-Vallée
5, boulevard Descartes
Champs sur Marne
77454 Marne-la-Vallée Cedex 2
Encadrement

Guillaume Blin - gblin@univ-mlv.fr
Stéphane Vialette - vialette@univ-mlv.fr

Présentation générale du domaine
Le stage proposé s'inscrit dans le domaine de l'algorithmique pour la bioinformatique. Le but est d'étudier la "faisabilité" algorithmique 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:

d'une suite S1 de bases, S1 étant construite sur l'alphabet {A, C, G, U }
d'un ensemble d'arcs P1 qui relient des paires de bases

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éciﬁques 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éciﬁque - mais il en existe bien d'autres...). On va donc chercher à déterminer la complexité du problème LAPCCS 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 éventuellement implémentés et testés sur des données réelles.

Bibliographie

P.A. Evans. Algorithms and Complexity for Annotated Sequence Analysis. PhD thesis, University of Victoria, 1999.
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.
Zeshan Peng. Structure Comparisons in Bioinformatics. PhD thesis, The University of Hong Kong, January 2006.
Yin-Te Tsai : The constrained longest common subsequence problem. Inf. Process. Lett. 88(4) : 173-176 (2003).
G. Blin. Combinatoire and Bio-informatique : Comparaison de structures d'ARN et calcul de distances intergénomiques. PhD thesis, Université de Nantes, 2005.

Professional training

Research interests

Projects

Software

Collaborators

CFP and conferences to come ...

Talks

Publications

Professional training