Approximating the number of double cut-and-join scenarios (Q441869): Difference between revisions
From MaRDI portal
Set profile property. |
Set OpenAlex properties. |
||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.tcs.2012.03.006 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2146844850 / rank | |||
Normal rank |
Revision as of 02:42, 20 March 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Approximating the number of double cut-and-join scenarios |
scientific article |
Statements
Approximating the number of double cut-and-join scenarios (English)
0 references
8 August 2012
0 references
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. The authors show the following results: 1) counting the number of optimal DCJ scenarios admits a fully polynomial time randomized approximation scheme (FPRAS); 2) there exists an MCMC uniform sampler that approximates this number; 3) this MCMC converges to the uniform distribution in fully polynomial time. In 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.
0 references
comparative genomics
0 references
genome rearrangement
0 references
FPRAS
0 references
DCJ
0 references
MCMC
0 references