Approximating the number of double cut-and-join scenarios (Q441869): Difference between revisions

From MaRDI portal
Import240304020342 (talk | contribs)
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
    0 references
    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

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references