## 99-10-068

Abstract:

#
Fast Fourier Transform for Fitness Landscapes

[PostScript]

##
Dan Rockmore, Peter Kostelec, Wim Hordijk, Peter F. Stadler

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 108
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}.

Submitted to *Appl.Math.Comput.*

**Keywords:**
Spectral analysis, Fast Fourier transform, Walsh functions, Cayley graphs,
fitness landscapes, assignment
problems, RNA folding.

Return to 1999 working papers list.