The evolution of the random reversal graph

DOI10.1016/J.AMC.2013.11.046zbMATH Open1365.92068arXiv1003.0739OpenAlexW2124013994WikidataQ56266974 ScholiaQ56266974MaRDI QIDQ2396473FDOQ2396473

Emma Yu Jin, Christian M. Reidys

Publication date: 8 June 2017

Published in: Applied Mathematics and Computation (Search for Journal in Brave)

Abstract: The random reversal graph offers new perspectives, allowing to study the connectivity of genomes as well as their most likely distance as a function of the reversal rate. Our main result shows that the structure of the random reversal graph changes dramatically at $$. For $$, the random graph consists of components of size at most $O(nln(n))$ a.s. and for $$, there emerges a unique largest component of size $simwp(epsilon)cdot{2}^{n}cdotn$!$ a.s.. This "giant" component is furthermore dense in the reversal graph.

Full work available at URL: https://arxiv.org/abs/1003.0739

Recommendations

• Genome Rearrangements and Sorting by Reversals
• scientific article; zbMATH DE number 1263193
• Sorting signed permutations by reversals, revisited
• Reversals Cayley graphs of symmetric groups
• On the expectation and variance of the reversal distance

zbMATH Keywords

permutationgiant componentreversalthreshold probability

Mathematics Subject Classification ID

Applications of graph theory (05C90) Genetics and epigenetics (92D10) Problems related to evolution (92D15)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Strong uniform times and finite random walks
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• Title not available (Why is that?)
• Title not available (Why is that?)
• The Evolution of Random Subgraphs of the Cube
• Large components in random induced subgraphs of \(n\)-cubes
• Transforming cabbage into turnip
• Largest random component of a k-cube
• Estimating true evolutionary distances between genomes
• Title not available (Why is that?)
• Vertex reconstruction in Cayley graphs

Cited In (1)

• The interchange process with reversals on the complete graph

This page was built for publication: The evolution of the random reversal graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2396473)