Counting, Generating, Analyzing and Sampling Tree Alignments

DOI10.1142/S0129054118420030MaRDI QIDQ4683230zbMATH OpenFDO

Authors Cedric Chauve, Julien Courtiel, Yann Ponty

Publication date 20 September 2018

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

zbMATH Keywords

analytic combinatoricsaverage-case complexity analysisGibbs-Boltzmann samplingtree alignments

Mathematics Subject Classification ID

Applications of graph theory (05C90) Exact enumeration problems, generating functions (05A15) Genetics and population dynamics (92D99)

Recommendations

• Counting, Generating and Sampling Tree Alignments
• Aligning sequences via an evolutionary tree: complexity and approximation
• Alignment-free phylogenetic reconstruction: Sample complexity via a branching process analysis
• Sampling motifs on phylogenetic trees
• Approximation algorithms for tree alignment with a given phylogeny
• Publication:4246780
• Simultaneous sequence alignment and tree construction using hidden Markov models
• Publication:4229084

Cites work

• scientific article; zbMATH DE number 986989 (Why is no real title available?)
• scientific article; zbMATH DE number 699389 (Why is no real title available?)
• A calculus for the random generation of labelled combinatorial structures
• A unified setting for sequencing, ranking, and selection algorithms for combinatorial objects
• Alignment of trees -- an alternative to tree edit
• Analytic combinatorics
• Average complexity of the Jiang-Wang-Zhang pairwise tree alignment algorithm and of an RNA secondary structure alignment algorithm
• Boltzmann Samplers for the Random Generation of Combinatorial Structures
• Boltzmann sampling of unlabelled structures
• CONTRAlign: Discriminative Training for Protein Sequence Alignment
• Consequences of Faster Alignment of Sequences
• Controlled non-uniform random generation of decomposable structures
• Counting, Generating and Sampling Tree Alignments
• Forest alignment with affine gaps and anchors, applied in RNA structure comparison
• Modeling dynamic programming problems over sequences and trees with inverse coupled rewrite systems
• The number of standard and of effective multiple alignments

Cited in

(4)

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

Describes a project that uses

Uses Software

• RNAforester
• CONTRAlign

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

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