Abstract
Protein structural alignment is an important problem in computational biology. In this paper, we present first successes on provably optimal pairwise alignment of protein inter-residue distance matrices, using the popular dali scoring function. We introduce the structural alignment problem formally, which enables us to express a variety of scoring functions used in previous work as special cases in a unified framework. Further, we propose the first mathematical model for computing optimal structural alignments based on dense inter-residue distance matrices. We therefore reformulate the problem as a special graph problem and give a tight integer linear programming model. We then present algorithm engineering techniques to handle the huge integer linear programs of real-life distance matrix alignment problems. Applying these techniques, we can compute provably optimal dali alignments for the very first time.
| Original language | English |
|---|---|
| Journal | Optimization Letters |
| Volume | 5 |
| Issue number | 3 |
| Pages (from-to) | 421-433 |
| Number of pages | 13 |
| ISSN | 1862-4472 |
| DOIs | |
| Publication status | Published - 08.2011 |
Funding
Acknowledgments This work has been supported by DFG grant KL 1390/2–1 and was partly done when I. Wohlers was visiting IRISA supported by an INRIA grant. R. Andonov is supported by BioWIC ANR-08-SEGI-005 project and partially by DVU-01/197/16.12.2008 NSF-Bulgaria. Computational experiments were sponsored by the NCF for the use of supercomputer facilities, with financial support from NWO.
