III: Small: Parameter Inference and Parameter Advising in Computational Biology

计算生物学研究人员经常需要从现有数据中重建未观察到的现象，例如一组物种的未知进化树，相关蛋白质序列的未知进化比对，或RNA分子的不可见折叠状态。寻找重建通常被建模为优化问题，其最优解旨在对应于正确的重建。这种模型中的一个关键因素是被优化的标准，它被目标函数捕获。该函数通常具有许多自由参数，并且这些参数的值的选择严重影响正确的重建是否实际上是最优解。该项目将建立一个通用软件系统，解决两个互补的问题：（1）参数推断，学习输入类的目标函数参数的最佳值，给出正确重建的例子;（2）参数建议，为特定输入推荐好的参数值。考虑一个软件工具的开发者和一个用户，他们解决了一个重建问题：参数推断为工具开发者找到最好的默认值，而参数建议为工具用户运行的特定输入找到好的特定值。参数推断将通过逆参数优化的最新算法突破来解决。给定重构问题的输入-输出对的示例，可以在多项式时间内找到使每个输出为其输入的最优解的目标函数的参数的值，只要：（a）目标函数在参数中是线性的，以及（B）当参数值固定时，重构问题是有效可解的。参数建议将通过以下方式解决：（1）学习将特征函数组合到重建精度估计器中的多项式，以及（2）从一组选择中选择参数值，以产生最高估计精度的重建。将通过整数线性规划找到使顾问平均真实精度最大化的最佳参数集。用于参数推断和咨询的通用软件系统将通过互联网作为开放源代码免费提供给研究人员。外展教育活动包括为高中生物和数学教师举办夏季研讨会，为他们的课堂开发生物信息学课程模块，并通过麦克奈尔学者计划指导经济困难和少数民族本科生。该项目开发的工具将对整个计算机科学产生非常广泛的影响，而不仅仅是计算生物学，因为最广泛使用的优化模型，如最短路径，最小生成树，最大匹配和网络流，都具有线性目标函数，参数推理技术适用于这些模型。

Computational biology researchers often need to reconstruct an unobserved phenomenon from available data, such as the unknown evolutionary tree for a set of species, the unknown evolutionary alignment of related protein sequences, or the unseen folded state of an RNA molecule. Finding the reconstruction is usually modeled as an optimization problem, whose optimal solution is intended to correspond to the correct reconstruction. A key ingredient in such a model is the criterion that is being optimized, which is captured by the objective function. This function often has many free parameters, and the choice of values for these parameters critically affects whether the correct reconstruction is actually an optimal solution. This project will build a general software system that solves two complementary problems: (1) parameter inference, which learns optimal values for the parameters of the objective function for classes of inputs, given examples of correct reconstructions; and (2) parameter advising, which recommends good values of the parameters for a specific input. Consider a developer and a user of a software tool that solves a reconstruction problem: parameter inference finds the best default values for the tool developer, while parameter advising finds good specific values for the particular input being run by the tool user.Parameter inference will be tackled via a recent algorithmic breakthrough in inverse parametric optimization. Given examples of input-output pairs for a reconstruction problem, values for the parameters of the objective function that make each output be an optimal solution for its input can be found in polynomial time, as long as: (a) the objective function is linear in the parameters, and (b) the reconstruction problem is efficiently solvable when parameter values are fixed. Parameter advising will be tackled by: (1) learning a polynomial that combines feature functions into an estimator for the accuracy of a reconstruction, and (2) selecting the parameter value from a set of choices that yields the reconstruction of highest estimated accuracy. An optimal parameter set that maximizes the average true accuracy of the advisor will be found by integer linear programming.The general software system for parameter inference and advising will be made freely available for researchers as open source through the Internet. Outreach educational activities include conducting a summer workshop for high school biology and mathematics teachers to develop bioinformatics curriculum modules for their classrooms, and mentoring economically disadvantaged and minority undergraduate students through the McNair Scholars program. The tools developed by the project are poised to have very broad impact throughout computer science, not just computational biology, as the most widely-used optimization models, such as shortest paths, minimum spanning trees, maximum matchings, and network flow, all have linear objective functions, to which the parameter inference techniques apply.