Counting and sampling SCJ small parsimony solutions

DOI10.1016/J.TCS.2014.07.027zbMATH Open1360.68483OpenAlexW2027203097MaRDI QIDQ740977FDOQ740977

István Miklós, Sándor Kiss, Eric Tannier

Publication date: 10 September 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2014.07.027

zbMATH Keywords

FPRASnon-approximabilitycounting problemscomputations on discrete structuresFPAUSsingle cut and join

Mathematics Subject Classification ID

Problems related to evolution (92D15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries
• The complexity of computing the permanent
• Random generation of combinatorial structures from a uniform distribution
• Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
• Approximating the number of double cut-and-join scenarios
• Bayesian Phylogenetic Inference from Animal Mitochondrial Genome Arrangements
• On the conductance of order Markov chains
• On weighted multiway cuts in trees
• Locating the vertices of a steiner tree in an arbitrary metric space

Cited In (3)

• Complexity and enumeration in models of genome rearrangement
• The computational complexity of calculating partition functions of optimal medians with Hamming distance
• Complexity and enumeration in models of genome rearrangement

Recommendations

• The phylogenetic effective sample size and jumps 👍 👎
• Complete Parsimony Haplotype Inference Problem and Algorithms 👍 👎
• Counting and optimising maximum phylogenetic diversity sets 👍 👎
• Counting, Generating and Sampling Tree Alignments 👍 👎
• Counting, Generating, Analyzing and Sampling Tree Alignments 👍 👎

This page was built for publication: Counting and sampling SCJ small parsimony solutions

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