Grammaires et s\'equences biologiques

De nombreux mod\`eles connus de repliement et/ou d'alignement de s\'equences biologiques peuvent \^etre d\'ecrits par un nouveau formalisme : les grammaires $S$-attribu\'ees multi-bandes (MTSAGs). Une fois impl\'ement\'e sous la forme d'un outil inspir\'e de YACC, ce formalisme fournit, \`a partir de la description formelle d'un mod\`ele, un programme dont les performances d\'epassent souvent celles d'un code C \'ecrit manuellement \`a partir d'une description moins formelle du mod\`ele. Les MTSAGs permettent d'am\'eliorer certains mod\`eles existants (Hidden Markov Models, Stochatic Context-Free Grammars, Covariance Models), et \'egalement de cr\'eer de nouveaux mod\`eles performants. La th\'orie permet de reconna\^\i tre certains langages non context-free \`a l'aide de MTSAGs, qui forment donc un sur-ensemble propre des grammaires context-free.