×

Integer linear programming in computational biology. (English) Zbl 1258.92013

Albers, Susanne (ed.) et al., Efficient algorithms. Essays dedicated to Kurt Mehlhorn on the occasion of his 60th birthday. Berlin: Springer (ISBN 978-3-642-03455-8/pbk). Lecture Notes in Computer Science 5760, 199-218 (2009).
Summary: Computational molecular biology (bioinformatics) is a young research field that is rich in NP-hard optimization problems. The problem instances encountered are often huge and comprise thousands of variables. Since their introduction into the field of bioinformatics in 1997, integer linear programming (ILP) techniques have been successfully applied to many optimization problems. These approaches have added much momentum to development and progress in related areas. In particular, ILP-based approaches have become a standard optimization technique in bioinformatics. In this review, we present applications of ILP-based techniques developed by members and former members of Kurt Mehlhorn’s group. These techniques were introduced to bioinformatics in a series of papers and popularized by demonstration of their effectiveness and potential.
For the entire collection see [Zbl 1175.68003].

MSC:

92C40 Biochemistry, molecular biology
90C10 Integer programming
90C05 Linear programming
92-08 Computational methods for problems pertaining to biology
92C42 Systems biology, networks
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alizadeh, F., Karp, R., Weisser, D., Zweig, G.: Physical mapping of chromosomes using unique probes. In: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 1994), pp. 489–500 (1994) · Zbl 0870.92005
[2] Reinert, K., Lenhof, H., Mutzel, P., Mehlhorn, K., Kececioglu, J.: A branch-and-cut algorithm for multiple sequence alignment. In: Proceedings of the First Annual International Conference on Computational Molecular Biology (RECOMB 1997), pp. 241–249 (1997) · doi:10.1145/267521.267845
[3] Christof, T., Jünger, M., Kececioglu, J., Mutzel, P., Reinelt, G.: A branch-and-cut approach to physical mapping with end-probes. In: Proceedings of the First Annual International Conference on Computational Molecular Biology (RECOMB 1997), pp. 84–92 (1997) · doi:10.1145/267521.267532
[4] Lenhof, H.P., Reinert, K., Vingron, M.: A polyhedral approach to RNA sequence structure alignment. In: Proceedings of the Second Annual International Conference on Computational Molecular Biology (RECOMB 1998), pp. 153–162 (1998) · doi:10.1145/279069.279109
[5] Althaus, E., Kohlbacher, O., Lenhof, H., Müller, P.: A combinatorial approach to protein docking with flexible side-chains. In: Proceedings of the Second Annual International Conference on Computational Molecular Biology (RECOMB 2000), pp. 15–24 (2000) · doi:10.1145/332306.332319
[6] Klau, G., Rahmann, S., Schliep, A., Vingron, M., Reinert, K.: Optimal robust non-unique probe selection using integer linear programming. Bioinformatics 20, i186–i193 (2004) · Zbl 1143.90020 · doi:10.1093/bioinformatics/bth936
[7] Dittrich, M., Klau, G.W., Rosenwald, A., Dandekar, T., Müller, T.: Identifying functional modules in protein-protein interaction networks: an integrated exact approach. Bioinformatics 24(13), i223 (2008) · doi:10.1093/bioinformatics/btn161
[8] Lancia, G.: Mathematical programming in computational biology: an annotated bibliography. Algorithms 1(2), 100–129 (2008) · Zbl 1461.90001 · doi:10.3390/a1020100
[9] Kececioglu, J.: The maximum weight trace problem in multiple sequence alignment. In: Apostolico, A., Crochemore, M., Galil, Z., Manber, U. (eds.) CPM 1993. LNCS, vol. 684, pp. 106–119. Springer, Heidelberg (1993) · doi:10.1007/BFb0029800
[10] Lenhof, H.P., Morgenstern, B., Reinert, K.: An exact solution for the segment-to-segment multiple sequence alignment problem. Bioinformatics 15(3), 203–210 (1999) · doi:10.1093/bioinformatics/15.3.203
[11] Althaus, E., Caprara, A., Lenhof, H.P., Reinert, K.: Multiple sequence alignment with arbitrary gap costs: Computing an optimal solution using polyhedral combinatorics. In: Proceedings of the 1st European Conference on Computational Biology (ECCB 2002), pp. 4–16 (2002) · doi:10.1093/bioinformatics/18.suppl_2.S4
[12] Althaus, E., Caprara, A., Lenhof, H.P., Reinert, K.: A branch-and-cut algorithm for multiple sequence alignment. Mathematical Programming 105, 387–425 (2006) · Zbl 1085.90060 · doi:10.1007/s10107-005-0659-3
[13] Althaus, E., Canzar, S.: A Lagrangian relaxation approach for the multiple sequence alignment problem. In: Dress, A.W.M., Xu, Y., Zhu, B. (eds.) COCOA 2007. LNCS, vol. 4616, pp. 267–278. Springer, Heidelberg (2007) · Zbl 1175.92016 · doi:10.1007/978-3-540-73556-4_29
[14] Althaus, E., Canzar, S.: A Lagrangian relaxation approach for the multiple sequence alignment problem. J. Combinat. Opt. 16(2), 127–154 (2008) · Zbl 1161.92027 · doi:10.1007/s10878-008-9139-z
[15] Fischetti, M., Lancia, G., Serafini, P.: Exact algorithms for minimum routing cost trees. Networks 39, 161–173 (2002) · Zbl 1027.90103 · doi:10.1002/net.10022
[16] Gusfield, D.: Efficient methods for multiple sequence alignment with guaranteed error bounds. Bulletin of Mathematical Biology 55, 141–154 (1993) · Zbl 0756.92020 · doi:10.1007/BF02460299
[17] Kececioglu, J., Kim, E.: Simple and fast inverse alignment. In: Apostolico, A., Guerra, C., Istrail, S., Pevzner, P.A., Waterman, M. (eds.) RECOMB 2006. LNCS (LNBI), vol. 3909, pp. 441–455. Springer, Heidelberg (2006) · Zbl 1302.92033 · doi:10.1007/11732990_37
[18] Mattick, J.S.: The functional genomics of noncoding RNA. Science 309(5740), 1527–1528 (2005) · doi:10.1126/science.1117806
[19] Goldman, D., Istrail, S., Papadimitriou, C.H.: Algorithmic aspects of protein structure similarity. In: FOCS, pp. 512–522 (1999) · doi:10.1109/SFFCS.1999.814624
[20] Wang, L., Jiang, T.: On the complexity of multiple sequence alignment. J. Comput. Biol. 1(4), 337–348 (1994) · doi:10.1089/cmb.1994.1.337
[21] Lancia, G., Carr, R., Walenz, B., Istrail, S.: 101 optimal PDB structure alignments: a branch-and-cut algorithm for the maximum contact map overlap problem. In: Proc. of the Fifth Annual International Conference on Computational Biology, pp. 193–202. ACM Press, New York (2001)
[22] Caprara, A., Lancia, G.: Structural Alignment of Large-Size Proteins via Lagrangian Relaxation. In: Proc. of RECOMB 2002, pp. 100–108. ACM Press, New York (2002)
[23] Caprara, A., Pisinger, D., Toth, P.: Exact solution of the quadratic knapsack problem. Informs J. on Computing 11(2), 125–137 (1999) · Zbl 1034.90521 · doi:10.1287/ijoc.11.2.125
[24] Carraresi, P., Malucelli, F.: A reformulation scheme and new lower bounds for the quadratic assignment problem. In: Quadratic Assignment and Related Topics. DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pp. 147–160. AMS Bookstore (1994) · Zbl 0817.90054
[25] Bauer, M., Klau, G.W.: Structural Alignment of Two RNA Sequences with Lagrangian Relaxation. In: Fleischer, R., Trippen, G. (eds.) ISAAC 2004. LNCS, vol. 3341, pp. 113–123. Springer, Heidelberg (2004) · Zbl 1116.92319 · doi:10.1007/978-3-540-30551-4_12
[26] Bauer, M., Klau, G.W., Reinert, K.: Multiple structural RNA alignment with Lagrangian relaxation. In: Casadio, R., Myers, G. (eds.) WABI 2005. LNCS (LNBI), vol. 3692, pp. 303–314. Springer, Heidelberg (2005) · doi:10.1007/11557067_25
[27] Bauer, M., Klau, G.W., Reinert, K.: An exact mathematical programming approach to multiple RNA sequence-structure alignment. Algorithmic Operations Research (2008); Special Issue on Biology, Medicine, and Health Care · Zbl 1277.90107
[28] Bauer, M., Klau, G.W., Reinert, K.: Accurate multiple sequence-structure alignment of RNA sequences using combinatorial optimization. BMC Bioinformatics 8(1), 271 (2007) · Zbl 05326324 · doi:10.1186/1471-2105-8-271
[29] Notredame, C., Higgins, D.G., Heringa, J.: T-Coffee: A novel method for fast and accurate multiple sequence alignment. Journal of Molecular Biology 302, 205–217 (2000) · doi:10.1006/jmbi.2000.4042
[30] Althaus, E., Kohlbacher, O., Lenhof, H.P., Müller, P.: A combinatorial approach to protein docking with flexible side-chains. J. Comput. Biol. 9(4), 597–612 (2002) · doi:10.1089/106652702760277336
[31] Eriksson, O., Zhou, Y., Elofsson, A.: Side-chain positioning as an integer programming problem. In: Gascuel, O., Moret, B.M.E. (eds.) WABI 2001. LNCS, vol. 2149, pp. 128–141. Springer, Heidelberg (2001) · Zbl 1128.90563 · doi:10.1007/3-540-44696-6_10
[32] Chazelle, B., Kingsford, C., Singh, M.: A semidefinite programming approach to side chain positioning with new rounding strategies. Informs J. Comput. 16, 380–392 (2004) · Zbl 1239.90083 · doi:10.1287/ijoc.1040.0096
[33] Kingsford, C., Chazelle, B., Singh, M.: Solving and analyzing side-chain positioning problems using linear and integer programming. Bioinformatics 21, 1028–1039 (2005) · doi:10.1093/bioinformatics/bti144
[34] Xu, J., Li, M., Kim, D., Xu, Y.: RAPTOR: optimal protein threading by linear programming. J. Bioinformatics Comput. Biol. 1(1), 95–117 (2003) · Zbl 02178419 · doi:10.1142/S0219720003000186
[35] Xu, J., Li, M.: Assessment of RAPTOR’s linear programming approach in CAFASP3. Proteins 53(suppl. 6), 579–584 (2003) · doi:10.1002/prot.10531
[36] Xu, J., Li, M., Xu, Y.: Protein threading by linear programming: theoretical analysis and computational results. J. Combinat. Opt. 8(4), 403–418 (2004) · Zbl 1079.90086 · doi:10.1007/s10878-004-4834-x
[37] Andonov, R., Balev, S., Yanev, N.: Protein threading: From mathematical models to parallel implementations. Informs J. Comput. 16(4), 393–405 (2004) · Zbl 1239.90011 · doi:10.1287/ijoc.1040.0092
[38] Veber, P., Yanev, N., Andonov, R., Poirriez, V.: Optimal protein threading by cost-splitting. In: Casadio, R., Myers, G. (eds.) WABI 2005. LNCS (LNBI), vol. 3692, pp. 365–375. Springer, Heidelberg (2005) · doi:10.1007/11557067_30
[39] Zhang, Z., Post, C.B., Smith, D.L.: Amide hydrogen exchange determined by mass spectrometry: application to rabbit muscle aldolase. Biochemistry 35, 779–791 (1996) · doi:10.1021/bi952227q
[40] Althaus, E., Canzar, S., Emmett, M.R., Karrenbauer, A., Marshall, A.G., Meyer-Baese, A., Zhang, H.: Computing H/D-exchange speeds of single residues from data of peptic fragments. In: Proceedings of the 23rd Annual ACM Symposium on Applied Computing, Fortaleza, Ceará, Brazil (2008) · doi:10.1145/1363686.1363981
[41] Althaus, E., Canzar, S., Ehrler, C., Emmett, M.R., Karrenbauer, A., Marshall, A.G., Meyer-Bäse, A., Tipton, J., Zhang, H.: Discrete fitting of hydrogen-deuterium-exchange-data of overlapping fragments. In: The 2009 International Conference on Bioinformatics & Computational Biology (in press, 2009) (accepted for publication)
[42] Klau, G.W., Rahmann, S., Schliep, A., Vingron, M., Reinert, K.: Optimal robust non-unique probe selection using integer linear programming. In: Proceedings of the Twelfth International Conference on Intelligent Systems for Molecular Biology (ISMB 2004), pp. 186–193 (2004) · Zbl 1143.90020 · doi:10.1093/bioinformatics/bth936
[43] Klau, G.W., Rahmann, S., Schliep, A., Vingron, M., Reinert, K.: Integer linear programming approaches for non-unique probe selection. Discrete Applied Mathematics 155, 840–856 (2007) · Zbl 1143.90020 · doi:10.1016/j.dam.2005.09.021
[44] Ideker, T., Ozier, O., Schwikowski, B., Siegel, A.F.: Discovering regulatory and signalling circuits in molecular interaction networks. Bioinformatics 18(suppl. 1), S233–S240 (2002) · doi:10.1093/bioinformatics/18.suppl_1.S233
[45] Klau, G.W.: A new graph-based method for pairwise global network alignment. BMC Bioinformatics 10(suppl. 1), S59 (2009) · Zbl 05739970 · doi:10.1186/1471-2105-10-S1-S59
[46] Toussaint, N.C., Dönnes, P., Kohlbacher, O.: A mathematical framework for the selection of an optimal set of peptides for epitope-based vaccines. PLoS Comput. Biol. 4(12), e1000246 (2008) · doi:10.1371/journal.pcbi.1000246
[47] Toussaint, N.C., Kohlbacher, O.: OptiTope – A web server for the selection of an optimal set of peptides for epitope-based vaccines. Nucl. Acids Res. (in press, 2009) · Zbl 05746779 · doi:10.1093/nar/gkp293
[48] Knuth, D.E.: Donald Knuth – Computer Literacy Bookshops Interview (1993), http://tex.loria.fr/historique/interviews/knuth-clb1993.html
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.