The evolution of the random reversal graph

DOI10.1016/J.AMC.2013.11.046MaRDI QIDQ2396473zbMATH OpenOpenAlexWikidataFDO

Authors Christian M. Reidys, Emma Yu Jin

Publication date 8 June 2017

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

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

zbMATH Keywords

permutationgiant componentreversalthreshold probability

Mathematics Subject Classification ID

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

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.

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

Cites work

• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 3978019 (Why is no real title available?)
• scientific article; zbMATH DE number 3313418 (Why is no real title available?)
• scientific article; zbMATH DE number 3190745 (Why is no real title available?)
• A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
• Combinatorics of genome rearrangements.
• Estimating true evolutionary distances between genomes
• Large components in random induced subgraphs of \(n\)-cubes
• Largest random component of a k-cube
• Strong uniform times and finite random walks
• The Evolution of Random Subgraphs of the Cube
• Transforming cabbage into turnip
• Vertex reconstruction in Cayley graphs

Cited in

(5)

• Reversals Cayley graphs of symmetric groups
• The spectral gap of graphs arising from substring reversals
• Effect of scale on long-range random graphs and chromosomal inversions
• The interchange process with reversals on the complete graph
• Uniquely pressable graphs: characterization, enumeration, and recognition

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)