Counting and sampling SCJ small parsimony solutions

DOI10.1016/J.TCS.2014.07.027MaRDI QIDQ740977zbMATHOpenAlexFDO

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

(4)

• Complexity and enumeration in models of genome rearrangement
• The computational complexity of calculating partition functions of optimal medians with Hamming distance
• Approximating the number of double cut-and-join scenarios
• Complexity and enumeration in models of genome rearrangement

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)