Counting, Generating, Analyzing and Sampling Tree Alignments

DOI10.1142/S0129054118420030zbMath1403.05013MaRDI QIDQ4683230

Julien Courtiel, Yann Ponty, Cedric Chauve

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)

Uses Software

• CONTRAlign
• RNAforester

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Forest alignment with affine gaps and anchors, applied in RNA structure comparison
• Alignment of trees -- an alternative to tree edit
• Controlled non-uniform random generation of decomposable structures
• Average complexity of the Jiang-Wang-Zhang pairwise tree alignment algorithm and of an RNA secondary structure alignment algorithm
• A unified setting for sequencing, ranking, and selection algorithms for combinatorial objects
• A calculus for the random generation of labelled combinatorial structures
• Modeling dynamic programming problems over sequences and trees with inverse coupled rewrite systems
• The number of standard and of effective multiple alignments
• Counting, Generating and Sampling Tree Alignments
• CONTRAlign: Discriminative Training for Protein Sequence Alignment
• Boltzmann Samplers for the Random Generation of Combinatorial Structures
• Consequences of Faster Alignment of Sequences
• Boltzmann Sampling of Unlabelled Structures