A. Abboud, V. V. Williams, and O. Weimann, Consequences of Faster Alignment of Sequences , Automata, Languages, and Programming: 41st International Colloquium, Proceedings, Part I eds, pp.2014-2053, 2014.

H. Andrade, I. Area, J. J. Nieto, and A. Torres, The number of reduced alignments between two DNA sequences, BMC Bioinformatics, vol.15, issue.1, p.94, 2014.
DOI : 10.1016/j.aml.2011.05.041

G. Blin, A. Denise, S. Dulucq, C. Herrbach, and H. Touzet, Alignments of RNA Structures, IEEE/ACM Transactions on Computational Biology and Bioinformatics, vol.7, issue.2, pp.309-322, 2010.
DOI : 10.1109/TCBB.2008.28
URL : https://hal.archives-ouvertes.fr/hal-00506348

A. Denise, Y. Ponty, and M. Termier, Controlled non-uniform random generation of decomposable structures, Theoretical Computer Science, vol.411, issue.40-42, pp.40-42, 2010.
DOI : 10.1016/j.tcs.2010.05.010
URL : https://hal.archives-ouvertes.fr/hal-00483581

C. Do, S. Gross, and S. Batzoglou, CONTRAlign: Discriminative Training for Protein Sequence Alignment, Research in Computational Molecular Biology Lecture Notes in Computer Science, vol.3909, pp.160-174, 2006.
DOI : 10.1007/11732990_15
URL : http://ai.stanford.edu/~chuongdo/papers/contralign.ps.gz

A. Dress, B. Morgenstern, and J. Stoye, The number of standard and of effective multiple alignments, Applied Mathematics Letters, vol.11, issue.4, pp.43-49, 1998.
DOI : 10.1016/S0893-9659(98)00054-8

M. Drmota, Systems of functional equations, Random Structures & Algorithms, vol.51, issue.1-2, pp.103-124, 1997.
DOI : 10.1002/(SICI)1098-2418(199701/03)10:1/2<103::AID-RSA5>3.0.CO;2-Z
URL : https://hal.archives-ouvertes.fr/hal-01197227

P. Duchon, P. Flajolet, G. Louchard, and G. Schaeffer, Boltzmann samplers for the random generation of combinatorial structures, Combinatorics, Probablity, and Computing, vol.13, pp.4-5, 2004.
URL : https://hal.archives-ouvertes.fr/hal-00307530

P. Flajolet, P. Zimmermann, and B. Van-cutsem, A calculus for the random generation of labelled combinatorial structures, Theoretical Computer Science, vol.132, issue.1-2, pp.1-35, 1994.
DOI : 10.1016/0304-3975(94)90226-7
URL : https://hal.archives-ouvertes.fr/hal-00917729

P. Flajolet, É. Fusy, and C. Pivoteau, Boltzmann Sampling of Unlabelled Structures, Proceedings of the Meeting on Analytic Algorithmics and Combinatorics, pp.201-211, 2007.
DOI : 10.1137/1.9781611972979.5
URL : https://hal.archives-ouvertes.fr/hal-00782866

P. Flajolet and R. Sedgewick, Analytic combinatorics, 2009.
DOI : 10.1017/CBO9780511801655
URL : https://hal.archives-ouvertes.fr/inria-00072739

R. Giegerich and H. Touzet, Modeling Dynamic Programming Problems over Sequences and Trees with Inverse Coupled Rewrite Systems, Algorithms, vol.7, issue.1, pp.62-144, 2014.
DOI : 10.3390/a7010062
URL : https://hal.archives-ouvertes.fr/hal-01084318

C. Herrbach, A. Denise, and S. Dulucq, Average complexity of the Jiang???Wang???Zhang pairwise tree alignment algorithm and of a RNA secondary structure alignment algorithm, Theoretical Computer Science, vol.411, issue.26-28, pp.26-28, 2010.
DOI : 10.1016/j.tcs.2010.01.014
URL : https://hal.archives-ouvertes.fr/hal-00665608

M. Höchsmann, T. Töller, R. Giegerich, and S. Kurtz, Local similarity in RNA secondary structures, Computational Systems Bioinformatics. CSB2003. Proceedings of the 2003 IEEE Bioinformatics Conference. CSB2003, pp.159-168, 2003.
DOI : 10.1109/CSB.2003.1227315

M. Höchsmann, B. Voss, and R. Giegerich, Pure multiple RNA secondary structure alignments: a progressive profile approach, IEEE/ACM Transactions on Computational Biology and Bioinformatics, vol.1, issue.1, pp.53-62, 2004.
DOI : 10.1109/TCBB.2004.11

T. Jiang, L. Wang, and K. Zhang, Alignment of trees ??? an alternative to tree edit, Theoretical Computer Science, vol.143, issue.1, pp.137-148, 1995.
DOI : 10.1016/0304-3975(95)80029-9

S. Needleman and C. Wunsch, A general method applicable to the search for similarities in the amino acid sequence of two proteins, Journal of Molecular Biology, vol.48, issue.3, pp.443-453, 1970.
DOI : 10.1016/0022-2836(70)90057-4

Y. Ponty and C. Saule, A Combinatorial Framework for Designing (Pseudoknotted) RNA Algorithms, Proceedings, pp.250-269, 2011.
DOI : 10.1093/nar/9.1.133
URL : https://hal.archives-ouvertes.fr/inria-00601060

G. Sauthoff, S. Janssen, and R. Giegerich, Bellman's GAP, Proceedings of the 13th international ACM SIGPLAN symposium on Principles and practices of declarative programming, PPDP '11, pp.29-40, 2011.
DOI : 10.1145/2003476.2003484

S. Schirmer and R. Giegerich, Forest Alignment with Affine Gaps and Anchors, RNA structure comparison, pp.51-67, 2013.
DOI : 10.1137/0218082

A. Torres, A. Cabada, and J. J. Nieto, An Exact Formula for the Number of Alignments Between Two DNA Sequences, DNA Sequence, vol.19, issue.6, pp.427-430, 2003.
DOI : 10.1080/10425170310001617894

M. Vingron and P. Argos, Determination of reliable regions in protein sequence alignments, "Protein Engineering, Design and Selection", vol.3, issue.7, pp.565-569, 1990.
DOI : 10.1093/protein/3.7.565

M. S. Waterman, Introduction to Computational Biology: Maps, Sequences and Genomes., Biometrics, vol.54, issue.1, 1995.
DOI : 10.2307/2534039

H. S. Wilf, A unified setting for sequencing, ranking, and selection algorithms for combinatorial objects, Advances in Mathematics, vol.24, issue.2, pp.281-291, 1977.
DOI : 10.1016/S0001-8708(77)80046-7
URL : http://doi.org/10.1016/s0001-8708(77)80046-7