基于动态规划算法的基因组邻近约束集覆盖问题优化解决方案及其在基因型组织表达谱估计中的应用

本研究针对基因型组织表达谱(GTEx)数据获取成本高的问题，创新性地将基因组邻近基因表达相似性转化为集覆盖问题。多伦多大学团队开发了基于动态规划的邻近集覆盖算法(Vicinity Set Cover)，在保证计算效率(O(n2))的同时获得最优解，可将人类基因组参考基因数量从18,078个减少至330个(阈值200k bps时)，平均估计误差控制在0.7±0.1。该研究为降低大规模RNA-seq实验成本提供了新思路，算法还可应用于相控阵天线优化等跨领域问题。

　　在基因组学研究领域，全面获取基因型组织表达谱(GTEx)一直是项耗资巨大的工程。GTEx项目需要对54种组织进行RNA测序(RNA-seq)，仅人类基因组就涉及18,078个蛋白编码基因的表达分析。更令人困扰的是，当研究新的模式生物或扩展人类组织类型时，这种全基因组规模的实验成本将呈几何级数增长。然而，近年研究发现了一个有趣现象：基因组位置邻近的基因往往表现出相似的表达模式，这种"邻近相似性"(vicinity similarity)为降低实验成本提供了可能——或许只需测量部分"参考基因"的表达谱，就能估算整个基因组的表达情况。

多伦多大学电气与计算机工程系的Jiahong Dong等研究人员在《Bioinformatics Advances》发表的研究，正是针对这一挑战提出了创新解决方案。研究团队发现，当基因间距在20-60k bps范围内时，无论顺反方向(sense/antisense)，其表达谱Pearson相关系数(PCC)都显著增高。这提示可以通过精心选择的参考基因集来估算全基因组表达谱，从而大幅减少实验测量需求。然而，将这一问题转化为传统的集覆盖问题(Set Cover Problem)时，现有算法面临两难：分支定界算法(Branch and Bound)虽能获得最优解但计算复杂度为NP难，而贪心算法(Greedy Algorithm)虽快却可能给出次优解。

研究采用GTEx v8和MESA小鼠表达数据集，通过计算基因间PCC量化表达相似性，并对表达谱进行log转换和z-score标准化处理。关键技术包括：1)基于转录起始/终止位点(TSS/TES)的邻近阈值定义；2)将基因组连续排序特性融入动态规划算法；3)开发兼顾集合数量最少和平均估计距离最小的优化策略。算法实现通过Python 3.9.7完成，代码已在GitHub开源。

【结果与讨论】

1. 估计误差与阈值关系
   研究发现表达谱估计误差与邻近阈值呈正相关。

   
   显示，当阈值从0增至200k bps时，仅估算基因的平均误差从0升至0.8，而包含参考基因的全基因组误差从0升至0.85。这种权衡关系为实验设计提供了量化依据。

2. 传统算法的局限性
   将基因邻近关系映射为集覆盖问题时，

   
   显示分支定界算法处理60个基因即需8小时，而贪心算法在34个基因测试中给出12个集合的次优解(最优解为11个)。

3. 动态规划算法优势
   提出的动态规划算法

   
   利用基因在基因组中的连续排序特性，将复杂度降至O(n²)。在染色体1(1,880基因)测试中，该算法与分支定界结果一致且速度快于贪心算法。

4. 最优路径选择标准
   当存在多个等优解时，

   
   显示选择平均估计距离最小的路径能进一步提升准确性。例如在t=12k bps时，最优路径的平均距离为19k bps。

该研究的创新价值体现在三方面：首先，为GTEx等大型转录组项目提供了降低成本的解决方案，例如在t=50k bps时仅需713个参考基因即可覆盖染色体1，平均误差0.64±0.12；其次，开发的算法可推广至单细胞测序等新兴数据；最后，提出的"邻近集覆盖问题"框架对天线布局优化等工程问题具有借鉴意义。未来研究可整合染色质开放程度(open chromatin)、拓扑关联域(TADs)等三维基因组特征进一步优化阈值选择策略。