Counting, generating and sampling tree alignments

Cedric Chauve 1 Julien Courtiel 1 Yann Ponty 2, 3
3 AMIB - Algorithms and Models for Integrative Biology
CNRS - Centre National de la Recherche Scientifique : UMR8623, X - École polytechnique, Inria Saclay - Ile de France, UP11 - Université Paris-Sud - Paris 11, LRI - Laboratoire de Recherche en Informatique, LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau]
Abstract : Pairwise ordered tree alignment are combinatorial objects that appear in RNA secondary structure comparison. However, the usual representation of tree alignments as supertrees is ambiguous, i.e. two distinct supertrees may induce identical sets of matches between identical pairs of trees. This ambiguity is uninformative, and detrimental to any probabilistic analysis. In this work, we consider tree alignments up to equivalence. Our first result is a precise asymptotic enumeration of tree alignments, obtained from a context-free grammar by mean of basic analytic combinatorics. Our second result focuses on alignments between two given ordered trees $S$ and $T$. By refining our grammar to align specific trees, we obtain a decomposition scheme for the space of alignments, and use it to design an efficient dynamic programming algorithm for sampling alignments under the Gibbs-Boltzmann probability distribution. This generalizes existing tree alignment algorithms, and opens the door for a probabilistic analysis of the space of suboptimal RNA secondary structures alignments.
Type de document :
Communication dans un congrès
Maria Boton-Fernandez; Carlos Martin-Vide; Sergio Santander-Jimenez; Miguel A. Vega-Rodriguez ALCOB - 3rd International Conference on Algorithms for Computational Biology - 2016, Jun 2016, Trujillo, Spain. Springer, LNCS, 9702, pp.53--64, 2016, 〈http://grammars.grlmc.com/AlCoB2016/〉. 〈10.1007/978-3-319-38827-4_5〉
Liste complète des métadonnées

https://hal.inria.fr/hal-01154030
Contributeur : Yann Ponty <>
Soumis le : dimanche 6 mars 2016 - 10:53:26
Dernière modification le : jeudi 10 mai 2018 - 02:06:52

Fichiers

CombinatoricsTreeAlignment-alc...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Cedric Chauve, Julien Courtiel, Yann Ponty. Counting, generating and sampling tree alignments. Maria Boton-Fernandez; Carlos Martin-Vide; Sergio Santander-Jimenez; Miguel A. Vega-Rodriguez ALCOB - 3rd International Conference on Algorithms for Computational Biology - 2016, Jun 2016, Trujillo, Spain. Springer, LNCS, 9702, pp.53--64, 2016, 〈http://grammars.grlmc.com/AlCoB2016/〉. 〈10.1007/978-3-319-38827-4_5〉. 〈hal-01154030v3〉

Partager

Métriques

Consultations de la notice

367

Téléchargements de fichiers

86