Counting, generating, analyzing and sampling tree alignments

Cedric Chauve 1 Julien Courtiel 2 Yann Ponty 3, 4
3 AMIB - Algorithms and Models for Integrative Biology
LIX - Laboratoire d'informatique de l'École polytechnique [Palaiseau], LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France
Abstract : Pairwise ordered tree alignment are combinatorial objects that appear in important applications , such as 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 alignments.
Type de document :
Article dans une revue
International Journal of Foundations of Computer Science, World Scientific Publishing, 2018
Liste complète des métadonnées

Littérature citée [24 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01500116
Contributeur : Yann Ponty <>
Soumis le : dimanche 2 avril 2017 - 12:50:39
Dernière modification le : mercredi 14 novembre 2018 - 16:08:07
Document(s) archivé(s) le : lundi 3 juillet 2017 - 13:20:51

Fichier

main.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité - Pas d'utilisation commerciale 4.0 International License

Identifiants

  • HAL Id : hal-01500116, version 1

Citation

Cedric Chauve, Julien Courtiel, Yann Ponty. Counting, generating, analyzing and sampling tree alignments. International Journal of Foundations of Computer Science, World Scientific Publishing, 2018. 〈hal-01500116〉

Partager

Métriques

Consultations de la notice

1353

Téléchargements de fichiers

109