Bilinear Programming and Protein Structure Alignment

Proteins are a primary functional component of organic life, and understanding their function is integral to many areas of research in biochemistry. The three-dimensional structure of a protein largely determines this function. Protein structure alignment compares the structure of a protein with known function to that of a protein with unknown function. A protein’s three-dimensional structure can be transformed through a smooth piecewise-linear sigmoid function to a real symmetric contact matrix that represents the functional significance of certain parts of the protein. We address the protein alignment problem as a minimization of the 2-norm difference of two proteins’ contact matrices. The minimization is presented as a bilinear program, and spectral bounds for best- and worst-case alignments are provided, which are continuous with respect to small changes in the protein’s structure. Further conditions for a perfect alignment and heuristics for finding quality solutions are given