Counting, Generating and Sampling Tree Alignments

DOI10.1007/978-3-319-38827-4_5zbMATH Open1346.92048DBLPconf/alcob/ChauveCP16arXiv1505.05983OpenAlexW2249602410WikidataQ57220962 ScholiaQ57220962MaRDI QIDQ2823014FDOQ2823014

Authors: Cedric Chauve, Yann Ponty, Julien Courtiel 

Publication date: 6 October 2016

Published in: Algorithms for Computational Biology (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1505.05983

Recommendations

• Counting, Generating, Analyzing and Sampling Tree Alignments
• Aligning sequences via an evolutionary tree: complexity and approximation
• Sampling motifs on phylogenetic trees
• Approximation algorithms for tree alignment with a given phylogeny
• Alignment-free phylogenetic reconstruction: Sample complexity via a branching process analysis
• Simultaneous sequence alignment and tree construction using hidden Markov models
• Generation of the exact distribution and simulation of matched nucleotide sequences on a phylogenetic tree
• Identifying consensus of trees through alignment

zbMATH Keywords

dynamic programmingRNA secondary structuretree alignment

Mathematics Subject Classification ID

Applications of graph theory (05C90) Protein sequences, DNA sequences (92D20)

Cites Work

• Analytic combinatorics
• A unified setting for sequencing, ranking, and selection algorithms for combinatorial objects
• Title not available (Why is that?)
• Forest alignment with affine gaps and anchors, applied in RNA structure comparison
• CONTRAlign: Discriminative Training for Protein Sequence Alignment
• Counting, Generating and Sampling Tree Alignments
• Average complexity of the Jiang-Wang-Zhang pairwise tree alignment algorithm and of an RNA secondary structure alignment algorithm
• The number of standard and of effective multiple alignments

Cited In (6)

• Generation of the exact distribution and simulation of matched nucleotide sequences on a phylogenetic tree
• Counting, Generating, Analyzing and Sampling Tree Alignments
• BayesCAT: Bayesian co-estimation of alignment and tree
• Counting and sampling SCJ small parsimony solutions
• Counting, Generating and Sampling Tree Alignments
• Algebraic dynamic programming on trees

Uses Software

• CONTRAlign
• RNAforester

This page was built for publication: Counting, Generating and Sampling Tree Alignments

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2823014)