À propos de mathématiques
Modèles combinatoires pour l’analyse de structures d’ARN
Touzet, Hélène1
1 LIFL - UMR CNRS 8022 - Université Lille 1
Femmes & math, Forum 8 des Jeunes Mathématiciennes, Tome 8 (2006), pp. 33-37.

Le but de cet exposé est de montrer comment des questions de biologie moléculaire peuvent faire émerger de nouveaux modèles combinatoires et de nouveaux algorithmes. Nous présentons plus particulièrement le problème de la comparaison de structures d’ARN,qui fait appel à des représentations sous forme d’arbres ordonnés ou de graphes particuliers, appelés séquences arc-annotées.

Publié le :
Touzet, Hélène 1

1 LIFL - UMR CNRS 8022 - Université Lille 1 
@article{RFM_2006__8__33_0,
     author = {Touzet, H\'el\`ene},
     title = {Mod\`eles combinatoires pour l{\textquoteright}analyse de structures {d{\textquoteright}ARN}},
     journal = {Femmes & math},
     pages = {33--37},
     publisher = {Association femmes et math\'ematiques},
     volume = {8},
     year = {2006},
     language = {fr},
     url = {http://www.numdam.org/item/RFM_2006__8__33_0/}
}
TY  - JOUR
AU  - Touzet, Hélène
TI  - Modèles combinatoires pour l’analyse de structures d’ARN
JO  - Femmes & math
PY  - 2006
SP  - 33
EP  - 37
VL  - 8
PB  - Association femmes et mathématiques
UR  - http://www.numdam.org/item/RFM_2006__8__33_0/
LA  - fr
ID  - RFM_2006__8__33_0
ER  - 
%0 Journal Article
%A Touzet, Hélène
%T Modèles combinatoires pour l’analyse de structures d’ARN
%J Femmes & math
%D 2006
%P 33-37
%V 8
%I Association femmes et mathématiques
%U http://www.numdam.org/item/RFM_2006__8__33_0/
%G fr
%F RFM_2006__8__33_0
Touzet, Hélène. Modèles combinatoires pour l’analyse de structures d’ARN. Femmes & math, Forum 8 des Jeunes Mathématiciennes, Tome 8 (2006), pp. 33-37. http://www.numdam.org/item/RFM_2006__8__33_0/

[1] J. Alber, J. Gramm, J. Guo et R. Niedermeier, Towards Optimally Solving the Longest Common Subsequence Problem for Sequences with Nested Arc Annotations in Linear Time LNCS 2373, p. 99 – 114, 2002 | MR | Zbl

[2] G. Blin, G. Fertin, I. Rusu et C. Sinoquet, RNA sequences and the EDIT(NESTED, NESTED) problem, rapport technique - LINA, Université de Nantes, 2003

[3] G. Blin et H. Touzet, How to compare arc-annotated sequences : the alignment hierarchy a paraitre dans les actes de SPIRE 2006, LNCS | MR | Zbl

[4] S. Dulucq et H. Touzet, Decomposition algorithms for the tree edit distance problem, Journal of Discrete Algorithms, 3(2-4), 2005, p. 448-471 | MR | Zbl

[5] P. Evans, Algorithms and Complexity for Annotated Sequences Analysis, PhD thesis, University of Victoria, 1999

[6] C. Herrbach, A. Denise, S. Dulucq et H. Touzet, A polynomial algorithm for comparing RNA secondary structures using a full set of operations. rapport technique LRI – Université Paris Sud, 2006

[7] J. Jansson et A. Lingas, A fast algorithm for optimal alignment between similar ordered trees, Fundamenta Informaticae 56-1(2), p. 105-120, 2003 | MR | Zbl

[8] T. Jiang, G. Lin, B. Ma et K. Zhang, A general edit distance between RNA structures, Journal of Computational Biology 9(2), p. 371-388, 2002

[9] T. Jiang, L. Wang et K. Zhang, Alignment of trees - an alternative to tree edit, Theoretical Computer Science, 143(1), p. 137-148, 1995 | MR | Zbl

[10] P. Klein, Computing the edit-distance between unrooted ordered trees, 1998, p. 91-102, 6th European Symposium on Algorithms | MR | Zbl

[11] G. Lin, Z.-Z. Chen, T. jiang et J. Wen, The longest common subsequence problem for sequences with nested arc annotations, J. of Computer and System Sciences, 65, 2002, p. 465-480 | MR | Zbl

[12] H. Touzet, A linear tree edit distance algorithm for similar ordered trees, CPM’05, Lecture Notes in Computer Science, 3537, p. 334-345, 2005 | Zbl