R语言下基因组场景带约束的Bin Packing问题求解思路与资源求助
R语言带基因组约束的变体装箱问题实现方案
问题梳理
需要将给定长度的基因组窗口随机分配到各染色体上,满足三个核心要求:
- 完全避开染色体上的不可用区域
- 尽可能多地放置所有待分配窗口
- 所有放置的窗口位置完全随机
已知输入数据
- 各染色体全长信息:
Chr1:1 - 200000 chr2:1 - 100000 . . .
- 各染色体不可用区域信息:
chr1: 100-200 chr1: 5000-5087 chr2: 1098-2067 . . .
- 待分配窗口长度列表:
3876 2000 10000 . . .
具体实现思路
步骤1:预处理可用区间
首先把每条染色体的全长区间减去所有不可用区间,得到所有连续的可用区间,直接过滤掉长度小于最短待分配窗口的区间,减少后续计算量。
推荐直接用GenomicRanges包处理:先把染色体全长、不可用区域都转成GRanges对象,用setdiff()方法就能快速得到所有可用区间。
步骤2:实现随机放置逻辑
如果需要自定义放置逻辑,按以下流程实现即可:
- 先打乱待分配窗口的顺序,保证放置的随机性
- 每次取出一个待分配窗口,按照可用区间的剩余长度做权重抽样,随机选中一个足够放下当前窗口的可用区间
- 在选中的可用区间内随机生成一个起始位点,保证窗口结束位点不超出区间边界、也不重叠不可用区域
- 放置完成后,把原可用区间拆成窗口前后的两个剩余区间,更新可用区间集合
- 重复上述流程直到没有可用区间能放下剩下的窗口
步骤3:提升放置数量的优化方案
如果优先保证放置最多窗口,可以调整放置顺序,优先放长度更长的窗口,避免短窗口占满空间后长窗口无法放置的情况。如果需要严格保证随机,就多次重复整个随机放置流程,取放置窗口数量最多的结果即可。
现成工具参考
不需要完全自定义的话,可以直接用regioneR包的randomizeRegions函数,原生支持指定禁止区域、自定义区间长度,直接把待分配窗口的长度作为参数传入,就能快速得到符合要求的随机放置结果。
内容的提问来源于stack exchange,提问作者Rachel Rap
相关产品推荐
相关产品推荐

