Approximating the number of double cut-and-join scenarios
type: Item
instance of: scholarly article
title: Approximating the number of double cut-and-join scenarios
zbMATH Open document ID: 1257.68074
author: István Miklós
author: Eric Tannier
published in: Theoretical Computer Science
publication date: 2012-08-08T00:00:00Z
reviewed by: Guillaume Fertin
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 92D10
Mathematics Subject Classification ID: 05C90
Mathematics Subject Classification ID: 60J10
zbMATH DE Number: 6064150
zbMATH Keywords: comparative genomics
zbMATH Keywords: genome rearrangement
zbMATH Keywords: FPRAS
zbMATH Keywords: DCJ
zbMATH Keywords: MCMC
MaRDI profile type: Publication
full work available at URL: j.tcs.2012.03.006
OpenAlex ID: W2146844850
cites work: Q4410146
cites work: Finding all sorting tandem duplication random loss operations
cites work: Geometric bounds for eigenvalues of Markov chains
cites work: Q3393448
cites work: Random generation of combinatorial structures from a uniform distribution
cites work: Bayesian Phylogenetic Inference from Animal Mitochondrial Genome Arrangements
cites work: Equation of State Calculations by Fast Computing Machines
cites work: Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow
DOI: 10.1016/J.TCS.2012.03.006
review text: In the present paper, the authors study the problem of counting the number of DCJ scenarios between two genomes represented as sets of paths and cycles. The problem is of importance: if determining the DCJ distance is easy (there exists a closed formula), knowing the number of scenarios that satisfy this distance, and, more importantly, being able to provide a sample of the most likely ones, is a problem that needs to be studied in more depth.NEWLINENEWLINEThe authors show the following results:NEWLINENEWLINE1) counting the number of optimal DCJ scenarios admits a fully polynomial time randomized approximation scheme (FPRAS);NEWLINENEWLINE2) there exists an MCMC uniform sampler that approximates this number;NEWLINENEWLINE3) this MCMC converges to the uniform distribution in fully polynomial time.NEWLINENEWLINEIn particular, the latter two results can be used to generate a sample of DCJ scenarios from a given distribution, in order to test some hypotheses on genome evolution. Due to the subjects covered by the authors in this paper, one needs to be familiar with genome rearrangements (and especially DCJ), complexity classes, and probabilities. However, the paper is cautiously written and is pleasant for the informed reader.
description: scientific article; zbMATH DE number 6064150