The ‘Butterfly effect’ in Cayley graphs with applications to genomics

摘要

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.