Title:
   Fast Fourier Transform for Fitness Landscapes

Author(s):
   Dan Rockmore, Peter Kostelec, Wim Hordijk, and Peter F. Stadler

Reference:
   Applied and Computational Harmonic Analysis, Volume 12, Number 1, 2002

Abstract:
   We cast some classes of fitness landscapes as problems in spectral analysis on various Cayley graphs. In particular, landscapes derived from RNA folding are realized on Hamming graphs and analyzed in terms of Walsh transforms; assignment problems are interpreted as functions on the symmetric group and analyzed in terms of the representation theory of S_n. We show that explicit computations of the Walsh/Fourier transforms are feasible for landscapes with up to 10⁸ configurations using Fast Fourier Transform techniques.

   We find that the cost function of a linear sum assignment problem involves only the defining representation of the symmetric group, while quadratic assignment problems are superpositions of the representations indexed by the partitions (n), (n - 1, 1), (n - 2, 2), and (n - 2, 1, 1). These correspond to the four smallest eigenvalues of the Laplacian of the Cayley graph obtained from using transpositions as the generating set on S_n.

Download:
   PostScript (gzip'ed; 131K)
   PDF (305K)

Other URLs:
   SFI working paper 99-10-068