Numerical Optimization in Bioinformatics

Florian Potra



In the post-genomic era, proteomics has become one of the most important research topics of modern science, opening new doors and potentially influencing medical science for years to come. By separating, cataloging, and comparing proteins from normal and diseased cells and tissues we gain invaluable knowledge about the changes taking place in complex biological systems at the molecular level, which in turn leads to better diagnostics and therapeutics. Two dimensional gel (2D Gel) electrophoresis, used in conjunction with a protein identification method such as mass spectrometry (MS), could provide the front end for a high-throughput analysis tool capable of comparing protein expression between large collections of samples. However the lack of reliable automated techniques for gel alignment, forms an important bottleneck to the large scale comparative studies that are necessary for fulfilling the potential of proteomics. In the talk we show that modern optimization techniques may be able to remove this bottleneck. We present new algorithms for image alignment of two-dimensional polyacrylamide electrophoresis (2D-PAGE) gels. In contrast with previous approaches that considered only pairwise alignment, we consider algorithms for the alignment of a whole collection of gels. A synthetic gel, containing some "ideal landmarks" is constructed together with a family of transformations, so that for each gel from the collection there is a unique transformation that maps that gel into the synthetic gel in such a way that the gel's landmarks are mapped into a very small neighborhoods of the corresponding ideal landmarks. Both the ideal landmarks and the family of transformations are obtained as the solution of a large-scale quadratic optimization problem which can be efficiently solved by interior-point methods.