



Towards an FPRAS on the number of optimal sorting reversal scenarios
- April 3, 2009
- 3:30 p.m.
- LeConte 112
Abstract
Although efficient algorithms are available to sort signed permutations with reversals in a most parsimonious way, little is known about the corresponding counting problem, namely obtaining the number of most parsimonious sorting scenarios of a given signed permutation. This counting problem is conjectured to be #P-complete, and our current research focuses on finding an FPRAS (Fully Polynomial Randomized Approximation Scheme) algorithm. Such FPRAS algorithms usually apply a quickly mixing Markov chain, and the number of solutions are approximated from the samples of the chain. In this talk I will prove that the commonly used strategy for building Markov chains yields a slowly mixing Markov chain. I will also present a novel approach. Although we couldn't prove that the mixing is always fast, we couldn't find a counterexample so far, and the implemented method seems quick on biological data.