III: Small: Exploiting and Extending Integer Linear Programming in Computational Biology

III：小：在计算生物学中利用和扩展整数线性规划

• 批准号: 1528234
• 负责人: Daniel Gusfield
• 金额: $ 39.81万
• 依托单位: University of California-Davis
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-09-01 至 2020-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1528234&HistoricalAwards=false
• 关键词: III; Small; Exploiting; Extending; Integer

Integer Linear Programming (ILP) is a versatile modeling and optimization technique that has been increasingly used in computational biology in inventive ways that differ from its traditional uses. Spectacular improvements in the speed of modern ILP solvers and computers now often allow the solution to important instances of hard computational problems that lack guaranteed-efficient solution methods. This project will further the exploitation of integer programming to solve realistic instances of computational problems in biology. The broader impact of this project will be through the improved computational tools that will be created for use in biology and perhaps medicine. This could have a transformative impact in biology. Broader impact will also be in the training of graduate and undergraduate students, and in outreach to biologists involved in computation. This project will also impact algorithmic computer science, by demonstrating a shift in emphasis from seeking worst-case efficient solutions or approximations to problem instances of all sizes and properties, to seeking methods that are effective in finding exact solutions to realistic problem instances of great importance.There are intellectual challenges in modeling biological phenomena for integer programming, non-trivial technical issues, and educational and outreach efforts needed to make the advances available to a larger biological community. The research questions are of three broad types: 1) Many research questions concern how to formulate, and more efficiently implement, a large succession of related ILP computations. This arises due to the need to evaluate the biological fidelity, and statistical significance, of a solution, often leading to changes in the biological model and ILP formulation, and many successive ILP computations. 2) It is often possible to devise mathematically-equivalent, but very different, ILP formulations for a computational problem, with large differences in the time and memory needed to solve the ILP instances. Many research questions concern how to devise the best ILP formulations for sub-classes of biological problems, and to identify successful new idioms (or modeling insights) that are common in these formulations. 3) Many technical issues come from the use of ILP as a language to express solutions to biological problems that are not naturally posed in terms of linear constraints. This exploits the fact that integer programming, being NP-hard, can express any problem in NP. However, the consequence is that the formulations are often non-intuitive, and huge in comparison to traditional ILP formulations, with a higher ratio of variables to equations than is expected by ILP solvers.

线性规划（ILP）是一种通用的建模和优化技术，越来越多地以不同于其传统用途的创造性方式用于计算生物学。现代ILP求解器和计算机的速度有了惊人的提高，现在通常可以解决缺乏高效求解方法的困难计算问题的重要实例。这个项目将进一步利用整数规划来解决生物学中计算问题的实际情况。该项目的更广泛影响将通过改进的计算工具来实现，这些工具将用于生物学，也许还有医学。这可能会对生物学产生变革性的影响。更广泛的影响也将在研究生和本科生的培训，并在推广到生物学家参与计算。这个项目也将影响算法计算机科学，通过展示重点从寻求最坏情况下的有效解决方案或近似的所有大小和属性的问题实例的转变，以寻求有效的方法来找到非常重要的现实问题实例的精确解决方案。需要开展教育和宣传工作，使更大的生物界能够利用这些进展。 研究问题有三大类：1）许多研究问题涉及如何制定，更有效地实现，大量的相关ILP计算的继承。这是由于需要评估解决方案的生物保真度和统计显著性，通常导致生物模型和ILP制剂的变化以及许多连续的ILP计算。2)对于计算问题，通常可以设计出等价但非常不同的ILP公式，其中解决ILP实例所需的时间和内存存在很大差异。许多研究问题涉及如何为生物学问题的子类设计最佳的ILP公式，并确定这些公式中常见的成功的新习惯用法（或建模见解）。3)许多技术问题来自于使用ILP作为一种语言来表达生物问题的解决方案，这些问题不是自然地以线性约束的形式提出的。这利用了这样一个事实：整数规划是NP难的，可以用NP来表达任何问题。然而，其结果是，公式往往是非直观的，和传统的ILP公式相比，巨大的，具有更高的比例的变量方程比ILP求解器的预期。