title: The 'Butterfly effect' in Cayley graphs with applications to genomics.
abstract: Suppose a finite set X is repeatedly transformed by a sequence of permutations of a certain type acting on an initial element x to produce a final state y. For example, in genomics applications, X could be a set of genomes and the permutations certain genome 'rearrangements' or, in group theory, X could be the set of configurations of a Rubik's cube and the permutations certain specified moves. We investigate how 'different' the resulting state y' to y can be if a slight change is made to the sequence, either by deleting one permutation, or replacing it with another. Here the 'difference' between y and y' might be measured by the minimum number of permutations of the permitted type required to transform y to y', or by some other metric. We discuss this first in the general setting of sensitivity to perturbation of walks in Cayley graphs of groups with a specified set of generators. We then investigate some permutation groups and generators arising in computational genomics, and the statistical implications of the findings.
authors.affiliation: School of Computing Sciences, University of East Anglia, Norwich NR4 7TJ, UK. vincent.moulton@cmp.uea.ac.uk
authors.forename: Vincent
authors.initials: V
authors.lastname: Moulton
authors.forename: Mike
authors.initials: M
authors.lastname: Steel
mesh_terms: D004247:DNA / Q000235:genetics*; D019143:Evolution, Molecular; D016678:Genome; D023281:Genomics / Q000379:methods*; D008957:Models, Genetic; D017354:Point Mutation; D013269:Stochastic Processes
chemical_list: D004247:DNA