代码之家 › 专栏 › 技术社区 › michaelmccarthy404

使用合成值的上限和下限实现硬币兑换算法

coin-change decomposition algorithm

michaelmccarthy404 · 技术社区 · 8 年前

我正在研究一个现实世界的问题,我有理论上的蛋白质序列和相关的实验蛋白质质量。我试图将实验蛋白质质量分解为已知质量的氨基酸的所有可能的复合物,以确定所有可能的杂质,这些杂质可能导致给定的实验蛋白质质量,将杂质定义为与理论蛋白质序列不同的任何复合物。

为了解决这个问题,我将其定义为硬币兑换问题,并实现了Bcker和Liptk在2005年的论文中概述的算法 Efficient Mass Decomposition .然而,我实现的算法识别了所有组件,并随着实验质量的大小呈指数级扩展,在用例中快速产生难以处理的结果。1000 Da的肽含有48530个复合物!

因为我不仅有实验肽质量,还有理论序列,我希望用实验序列来缩小输出复合物的范围,并希望对返回的复合物设定一个上限。例如,如果我有一个包含2个As、3个Cs和5个Ds的理论序列,我会将限制设置为double,这样返回的compomer不能超过4个As、6个Cs和10个Ds。在解决硬币兑换问题时,有可能实现这样的上限吗?有没有更好或更有效的方法来解决这个问题?

0 回复 | 直到 8 年前

推荐文章

Matthew Thomas · 在每个决策中给出多个选择的所有可能的决策路径/结果

1 年前

feasega · 聚合物模拟-2个节点之间的最短路线,适用于所有节点

1 年前

Alisa Petrova · 在有向图中更改一对顶点以创建循环

1 年前

Matvey Androsyuk · 如何使用React在树结构中呈现我的组件,就像IDE中的默认文件结构一样

1 年前

Pengcheng · 这个简单的递归函数的输出是什么?你能详细解释一下吗?

1 年前

b39b332d · 使用C++标准库实现高效间隔存储

2 年前

Paul C · 在维基百科上,将二叉搜索树转换为排序链表的算法是否存在错误?

2 年前

ABGR · 二叉树的直径——当最长路径不通过根时的失败案例

2 年前

SHUBHAM KUMAR · 这两个是否完全相同-->“下限(股份有限公司rbegin(),股份有限公司rend(),i,更大<int>())”和“下限(dec.begin(

2 年前

EpicAshman · 数独棋盘程序中同一列和同一行出现两次的数字

2 年前