{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,9]],"date-time":"2025-09-09T22:00:13Z","timestamp":1757455213251},"publisher-location":"Berlin, Heidelberg","reference-count":49,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642034558"},{"type":"electronic","value":"9783642034565"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-03456-5_14","type":"book-chapter","created":{"date-parts":[[2009,8,31]],"date-time":"2009-08-31T22:39:16Z","timestamp":1251758356000},"page":"199-218","source":"Crossref","is-referenced-by-count":7,"title":["Integer Linear Programming in Computational Biology"],"prefix":"10.1007","author":[{"given":"Ernst","family":"Althaus","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gunnar W.","family":"Klau","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Oliver","family":"Kohlbacher","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hans-Peter","family":"Lenhof","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Knut","family":"Reinert","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"14_CR1","unstructured":"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\u2013500 (1994)"},{"key":"14_CR2","doi-asserted-by":"crossref","unstructured":"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\u2013249 (1997)","DOI":"10.1145\/267521.267845"},{"key":"14_CR3","doi-asserted-by":"crossref","unstructured":"Christof, T., J\u00fcnger, 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\u201392 (1997)","DOI":"10.1145\/267521.267532"},{"key":"14_CR4","doi-asserted-by":"crossref","unstructured":"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\u2013162 (1998)","DOI":"10.1145\/279069.279109"},{"key":"14_CR5","doi-asserted-by":"crossref","unstructured":"Althaus, E., Kohlbacher, O., Lenhof, H., M\u00fcller, 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\u201324 (2000)","DOI":"10.1145\/332306.332319"},{"key":"14_CR6","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1093\/bioinformatics\/bth936","volume":"20","author":"G. Klau","year":"2004","unstructured":"Klau, G., Rahmann, S., Schliep, A., Vingron, M., Reinert, K.: Optimal robust non-unique probe selection using integer linear programming. Bioinformatics\u00a020, i186\u2013i193 (2004)","journal-title":"Bioinformatics"},{"issue":"13","key":"14_CR7","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1093\/bioinformatics\/btn161","volume":"24","author":"M. Dittrich","year":"2008","unstructured":"Dittrich, M., Klau, G.W., Rosenwald, A., Dandekar, T., M\u00fcller, T.: Identifying functional modules in protein-protein interaction networks: an integrated exact approach. Bioinformatics\u00a024(13), i223 (2008)","journal-title":"Bioinformatics"},{"issue":"2","key":"14_CR8","doi-asserted-by":"publisher","first-page":"100","DOI":"10.3390\/a1020100","volume":"1","author":"G. Lancia","year":"2008","unstructured":"Lancia, G.: Mathematical programming in computational biology: an annotated bibliography. Algorithms\u00a01(2), 100\u2013129 (2008)","journal-title":"Algorithms"},{"key":"14_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"106","DOI":"10.1007\/BFb0029800","volume-title":"Combinatorial Pattern Matching","author":"J. Kececioglu","year":"1993","unstructured":"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.\u00a0684, pp. 106\u2013119. Springer, Heidelberg (1993)"},{"issue":"3","key":"14_CR10","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1093\/bioinformatics\/15.3.203","volume":"15","author":"H.P. Lenhof","year":"1999","unstructured":"Lenhof, H.P., Morgenstern, B., Reinert, K.: An exact solution for the segment-to-segment multiple sequence alignment problem. Bioinformatics\u00a015(3), 203\u2013210 (1999)","journal-title":"Bioinformatics"},{"key":"14_CR11","doi-asserted-by":"crossref","unstructured":"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\u201316 (2002)","DOI":"10.1093\/bioinformatics\/18.suppl_2.S4"},{"key":"14_CR12","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/s10107-005-0659-3","volume":"105","author":"E. Althaus","year":"2006","unstructured":"Althaus, E., Caprara, A., Lenhof, H.P., Reinert, K.: A branch-and-cut algorithm for multiple sequence alignment. Mathematical Programming\u00a0105, 387\u2013425 (2006)","journal-title":"Mathematical Programming"},{"key":"14_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1007\/978-3-540-73556-4_29","volume-title":"Combinatorial Optimization and Applications","author":"E. Althaus","year":"2007","unstructured":"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.\u00a04616, pp. 267\u2013278. Springer, Heidelberg (2007)"},{"issue":"2","key":"14_CR14","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/s10878-008-9139-z","volume":"16","author":"E. Althaus","year":"2008","unstructured":"Althaus, E., Canzar, S.: A Lagrangian relaxation approach for the multiple sequence alignment problem. J. Combinat. Opt.\u00a016(2), 127\u2013154 (2008)","journal-title":"J. Combinat. Opt."},{"key":"14_CR15","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1002\/net.10022","volume":"39","author":"M. Fischetti","year":"2002","unstructured":"Fischetti, M., Lancia, G., Serafini, P.: Exact algorithms for minimum routing cost trees. Networks\u00a039, 161\u2013173 (2002)","journal-title":"Networks"},{"key":"14_CR16","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/BF02460299","volume":"55","author":"D. Gusfield","year":"1993","unstructured":"Gusfield, D.: Efficient methods for multiple sequence alignment with guaranteed error bounds. Bulletin of Mathematical Biology\u00a055, 141\u2013154 (1993)","journal-title":"Bulletin of Mathematical Biology"},{"key":"14_CR17","series-title":"Lecture Notes in Bioinformatics","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1007\/11732990_37","volume-title":"Research in Computational Molecular Biology","author":"J. Kececioglu","year":"2006","unstructured":"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.\u00a03909, pp. 441\u2013455. Springer, Heidelberg (2006)"},{"issue":"5740","key":"14_CR18","doi-asserted-by":"publisher","first-page":"1527","DOI":"10.1126\/science.1117806","volume":"309","author":"J.S. Mattick","year":"2005","unstructured":"Mattick, J.S.: The functional genomics of noncoding RNA. Science\u00a0309(5740), 1527\u20131528 (2005)","journal-title":"Science"},{"key":"14_CR19","doi-asserted-by":"crossref","unstructured":"Goldman, D., Istrail, S., Papadimitriou, C.H.: Algorithmic aspects of protein structure similarity. In: FOCS, pp. 512\u2013522 (1999)","DOI":"10.1109\/SFFCS.1999.814624"},{"issue":"4","key":"14_CR20","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1089\/cmb.1994.1.337","volume":"1","author":"L. Wang","year":"1994","unstructured":"Wang, L., Jiang, T.: On the complexity of multiple sequence alignment. J. Comput. Biol.\u00a01(4), 337\u2013348 (1994)","journal-title":"J. Comput. Biol."},{"key":"14_CR21","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1145\/369133.369199","volume-title":"Proc. of the Fifth Annual International Conference on Computational Biology","author":"G. Lancia","year":"2001","unstructured":"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\u2013202. ACM Press, New York (2001)"},{"key":"14_CR22","first-page":"100","volume-title":"Proc. of RECOMB 2002","author":"A. Caprara","year":"2002","unstructured":"Caprara, A., Lancia, G.: Structural Alignment of Large-Size Proteins via Lagrangian Relaxation. In: Proc. of RECOMB 2002, pp. 100\u2013108. ACM Press, New York (2002)"},{"issue":"2","key":"14_CR23","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1287\/ijoc.11.2.125","volume":"11","author":"A. Caprara","year":"1999","unstructured":"Caprara, A., Pisinger, D., Toth, P.: Exact solution of the quadratic knapsack problem. Informs J. on Computing\u00a011(2), 125\u2013137 (1999)","journal-title":"Informs J. on Computing"},{"key":"14_CR24","doi-asserted-by":"crossref","unstructured":"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\u2013160. AMS Bookstore (1994)","DOI":"10.1090\/dimacs\/016\/06"},{"key":"14_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1007\/978-3-540-30551-4_12","volume-title":"Algorithms and Computation","author":"M. Bauer","year":"2004","unstructured":"Bauer, M., Klau, G.W.: Structural Alignment of Two RNA Sequences with Lagrangian Relaxation. In: Fleischer, R., Trippen, G. (eds.) ISAAC 2004. LNCS, vol.\u00a03341, pp. 113\u2013123. Springer, Heidelberg (2004)"},{"key":"14_CR26","series-title":"Lecture Notes in Bioinformatics","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1007\/11557067_25","volume-title":"Algorithms in Bioinformatics","author":"M. Bauer","year":"2005","unstructured":"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.\u00a03692, pp. 303\u2013314. Springer, Heidelberg (2005)"},{"key":"#cr-split#-14_CR27.1","unstructured":"Bauer, M., Klau, G.W., Reinert, K.: An exact mathematical programming approach to multiple RNA sequence-structure alignment. Algorithmic Operations Research (2008);"},{"key":"#cr-split#-14_CR27.2","unstructured":"Special Issue on Biology, Medicine, and Health Care"},{"issue":"1","key":"14_CR28","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1186\/1471-2105-8-271","volume":"8","author":"M. Bauer","year":"2007","unstructured":"Bauer, M., Klau, G.W., Reinert, K.: Accurate multiple sequence-structure alignment of RNA sequences using combinatorial optimization. BMC Bioinformatics\u00a08(1), 271 (2007)","journal-title":"BMC Bioinformatics"},{"key":"14_CR29","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1006\/jmbi.2000.4042","volume":"302","author":"C. Notredame","year":"2000","unstructured":"Notredame, C., Higgins, D.G., Heringa, J.: T-Coffee: A novel method for fast and accurate multiple sequence alignment. Journal of Molecular Biology\u00a0302, 205\u2013217 (2000)","journal-title":"Journal of Molecular Biology"},{"issue":"4","key":"14_CR30","doi-asserted-by":"publisher","first-page":"597","DOI":"10.1089\/106652702760277336","volume":"9","author":"E. Althaus","year":"2002","unstructured":"Althaus, E., Kohlbacher, O., Lenhof, H.P., M\u00fcller, P.: A combinatorial approach to protein docking with flexible side-chains. J. Comput. Biol.\u00a09(4), 597\u2013612 (2002)","journal-title":"J. Comput. Biol."},{"key":"14_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1007\/3-540-44696-6_10","volume-title":"Algorithms in Bioinformatics","author":"O. Eriksson","year":"2001","unstructured":"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.\u00a02149, pp. 128\u2013141. Springer, Heidelberg (2001)"},{"key":"14_CR32","doi-asserted-by":"publisher","first-page":"380","DOI":"10.1287\/ijoc.1040.0096","volume":"16","author":"B. Chazelle","year":"2004","unstructured":"Chazelle, B., Kingsford, C., Singh, M.: A semidefinite programming approach to side chain positioning with new rounding strategies. Informs J. Comput.\u00a016, 380\u2013392 (2004)","journal-title":"Informs J. Comput."},{"key":"14_CR33","doi-asserted-by":"publisher","first-page":"1028","DOI":"10.1093\/bioinformatics\/bti144","volume":"21","author":"C. Kingsford","year":"2005","unstructured":"Kingsford, C., Chazelle, B., Singh, M.: Solving and analyzing side-chain positioning problems using linear and integer programming. Bioinformatics\u00a021, 1028\u20131039 (2005)","journal-title":"Bioinformatics"},{"issue":"1","key":"14_CR34","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1142\/S0219720003000186","volume":"1","author":"J. Xu","year":"2003","unstructured":"Xu, J., Li, M., Kim, D., Xu, Y.: RAPTOR: optimal protein threading by linear programming. J. Bioinformatics Comput. Biol.\u00a01(1), 95\u2013117 (2003)","journal-title":"J. Bioinformatics Comput. Biol."},{"issue":"suppl. 6","key":"14_CR35","doi-asserted-by":"publisher","first-page":"579","DOI":"10.1002\/prot.10531","volume":"53","author":"J. Xu","year":"2003","unstructured":"Xu, J., Li, M.: Assessment of RAPTOR\u2019s linear programming approach in CAFASP3. Proteins\u00a053(suppl. 6), 579\u2013584 (2003)","journal-title":"Proteins"},{"issue":"4","key":"14_CR36","doi-asserted-by":"publisher","first-page":"403","DOI":"10.1007\/s10878-004-4834-x","volume":"8","author":"J. Xu","year":"2004","unstructured":"Xu, J., Li, M., Xu, Y.: Protein threading by linear programming: theoretical analysis and computational results. J. Combinat. Opt.\u00a08(4), 403\u2013418 (2004)","journal-title":"J. Combinat. Opt."},{"issue":"4","key":"14_CR37","doi-asserted-by":"publisher","first-page":"393","DOI":"10.1287\/ijoc.1040.0092","volume":"16","author":"R. Andonov","year":"2004","unstructured":"Andonov, R., Balev, S., Yanev, N.: Protein threading: From mathematical models to parallel implementations. Informs J. Comput.\u00a016(4), 393\u2013405 (2004)","journal-title":"Informs J. Comput."},{"key":"14_CR38","series-title":"Lecture Notes in Bioinformatics","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/11557067_30","volume-title":"Algorithms in Bioinformatics","author":"P. Veber","year":"2005","unstructured":"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.\u00a03692, pp. 365\u2013375. Springer, Heidelberg (2005)"},{"key":"14_CR39","doi-asserted-by":"publisher","first-page":"779","DOI":"10.1021\/bi952227q","volume":"35","author":"Z. Zhang","year":"1996","unstructured":"Zhang, Z., Post, C.B., Smith, D.L.: Amide hydrogen exchange determined by mass spectrometry: application to rabbit muscle aldolase. Biochemistry\u00a035, 779\u2013791 (1996)","journal-title":"Biochemistry"},{"key":"14_CR40","doi-asserted-by":"crossref","unstructured":"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\u00e1, Brazil (2008)","DOI":"10.1145\/1363686.1363981"},{"key":"14_CR41","unstructured":"Althaus, E., Canzar, S., Ehrler, C., Emmett, M.R., Karrenbauer, A., Marshall, A.G., Meyer-B\u00e4se, 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)"},{"key":"14_CR42","doi-asserted-by":"crossref","unstructured":"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\u2013193 (2004)","DOI":"10.1093\/bioinformatics\/bth936"},{"key":"14_CR43","doi-asserted-by":"publisher","first-page":"840","DOI":"10.1016\/j.dam.2005.09.021","volume":"155","author":"G.W. Klau","year":"2007","unstructured":"Klau, G.W., Rahmann, S., Schliep, A., Vingron, M., Reinert, K.: Integer linear programming approaches for non-unique probe selection. Discrete Applied Mathematics\u00a0155, 840\u2013856 (2007)","journal-title":"Discrete Applied Mathematics"},{"issue":"suppl. 1","key":"14_CR44","doi-asserted-by":"publisher","first-page":"233","DOI":"10.1093\/bioinformatics\/18.suppl_1.S233","volume":"18","author":"T. Ideker","year":"2002","unstructured":"Ideker, T., Ozier, O., Schwikowski, B., Siegel, A.F.: Discovering regulatory and signalling circuits in molecular interaction networks. Bioinformatics\u00a018(suppl. 1), S233\u2013S240 (2002)","journal-title":"Bioinformatics"},{"issue":"suppl. 1","key":"14_CR45","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1186\/1471-2105-10-S1-S59","volume":"10","author":"G.W. Klau","year":"2009","unstructured":"Klau, G.W.: A new graph-based method for pairwise global network alignment. BMC Bioinformatics\u00a010(suppl. 1), S59 (2009)","journal-title":"BMC Bioinformatics"},{"issue":"12","key":"14_CR46","doi-asserted-by":"publisher","first-page":"1000246","DOI":"10.1371\/journal.pcbi.1000246","volume":"4","author":"N.C. Toussaint","year":"2008","unstructured":"Toussaint, N.C., D\u00f6nnes, P., Kohlbacher, O.: A mathematical framework for the selection of an optimal set of peptides for epitope-based vaccines. PLoS Comput. Biol.\u00a04(12), e1000246 (2008)","journal-title":"PLoS Comput. Biol."},{"key":"14_CR47","doi-asserted-by":"crossref","unstructured":"Toussaint, N.C., Kohlbacher, O.: OptiTope \u2013 A web server for the selection of an optimal set of peptides for epitope-based vaccines. Nucl. Acids Res. (in press, 2009)","DOI":"10.1093\/nar\/gkp293"},{"key":"14_CR48","unstructured":"Knuth, D.E.: Donald Knuth \u2013 Computer Literacy Bookshops Interview (1993), http:\/\/tex.loria.fr\/historique\/interviews\/knuth-clb1993.html"}],"container-title":["Lecture Notes in Computer Science","Efficient Algorithms"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-03456-5_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,10]],"date-time":"2021-10-10T02:42:35Z","timestamp":1633833755000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-03456-5_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642034558","9783642034565"],"references-count":49,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-03456-5_14","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}