A Fourier Tour of Protein Function Prediction

Predicting the biological functions of proteins from their amino acid sequences is one of the long-standing challenges in biology. A comprehensive solution has remained elusive due to the vastness of the combinatorial space of sequences and our limited ability to probe the space experimentally. In this talk, we view protein function prediction from a signal recovery and information theory perspective through the lens of the Fourier transform—also known as Walsh-Hadamard (WH) transform for sequence functions. We discuss how WH transform allows us to view protein functions as a multilinear polynomial and in terms of high-order sparse nonlinear interactions. We demonstrate that an intuitive divide-and-conquer strategy can find the polynomial using a number of samples and times that grows only linearly with the length of the protein sequence. Next, we discuss how we can leverage natural assumptions about the polynomial, such as sparsity, to develop efficient protein function prediction algorithms rooted inc oding theory.