Counting and sampling SCJ small parsimony solutions

DOI10.1016/J.TCS.2014.07.027MaRDI QIDQ740977zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

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

Cites work

• scientific article; zbMATH DE number 3888913 (Why is no real title available?)
• scientific article; zbMATH DE number 1945172 (Why is no real title available?)
• scientific article; zbMATH DE number 3070115 (Why is no real title available?)
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
• Approximating the number of double cut-and-join scenarios
• Bayesian Phylogenetic Inference from Animal Mitochondrial Genome Arrangements
• Combinatorics of genome rearrangements.
• Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
• Locating the vertices of a steiner tree in an arbitrary metric space
• On the conductance of order Markov chains
• On weighted multiway cuts in trees
• Random generation of combinatorial structures from a uniform distribution
• The complexity of computing the permanent

Cited in

(6)

• The computational complexity of calculating partition functions of optimal medians with Hamming distance
• Complexity and enumeration in models of genome rearrangement
• Approximating the number of double cut-and-join scenarios
• Complexity and enumeration in models of genome rearrangement
• Pairwise rearrangement is fixed-parameter tractable in the single cut-and-join model
• Pairwise rearrangement is fixed-parameter tractable in the single cut-and-Join model

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)