A polynomial-delay algorithm for enumerating approximate solutions to the interval constrained coloring problem
A polynomial-delay algorithm for enumerating approximate solutions to the interval constrained coloring problem
复制标题
枚举区间约束着色问题近似解的多项式延迟算法
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Julián Mestre
中科院分区：
文献类型：
--
作者：
S. Canzar;Khaled M. Elbassioni;Julián Mestre
我们研究了间隔的约束着色问题，这是一个组合问题，它是在基于氢/氘交换和质谱法的实验中产生的蛋白质结构数据的解释。该问题抓住了增加实验数据空间分辨率的挑战性任务，以便更好地了解蛋白质结构。由于任何算法框架提出的解决方案最终都必须由生物化学家验证，因此不仅提供单个解决方案，而且提供一套有价值的候选解决方案，这一点很重要。我们的贡献是用于列举所有精确溶液加上进一步近似溶液的多项式 - 延迟，多项式空间算法，保证在蛋白质片段内的两个最佳的绝对误差范围内，即在连续残基的一组中。我们的实验表明，近似解决方案的质量在与基础真实解决方案的偏差方面相当。此外，与整数编程求解器相比，实验还确认了该方法在大大减少两种连续解决方案之间的延迟方面的有效性。
We study the interval constrained coloring problem, a combinatorial problem arising in the interpretation of data on protein structure emanating from experiments based on hydrogen/deuterium exchange and mass spectrometry. The problem captures the challenging task of increasing the spatial resolution of experimental data in order to get a better picture of the protein structure. Since solutions proposed by any algorithmic framework have to ultimately be verified by biochemists, it is important to provide not just a single solution, but a valuable set of candidate solutions. Our contribution is a polynomial-delay, polynomial-space algorithm for enumerating all exact solutions plus further approximate solutions, which are guaranteed to be within an absolute error of two of the optimum within fragments of the protein, that is, within sets of consecutive residues. Our experiments indicate that the quality of the approximate solutions is comparable to the optimal ones in terms of deviation from the underlying true solution. In addition, the experiments also confirm the effectiveness of the method in reducing the delay between two consecutive solutions considerably, compared to what it takes an integer programming solver to produce the next exact solution.
影响因子：
2.9
作者：
Zuiderweg, ERP
通讯作者：
Zuiderweg, ERP