基于平衡恒重格雷码的误差检测组合池化实验新方法及其在生物医学高通量检测中的应用

《Bioinformatics》：Unbiased and Error-Detecting Combinatorial Pooling Experiments with Balanced Constant-Weight Gray Codes for Consecutive Positives Detection

本研究针对生物组合池化实验中样本分布不均、连续阳性检测困难及误差控制不足等问题，提出了一种基于平衡恒重格雷码（DCP-CWGC）的新型组合池化设计方案。通过分支定界算法（BBA）和递归组合算法（rcBBA）构建的DCP-CWGC码，实现了样本在池中的均匀分布、连续阳性样本的精准识别及实验误差的有效检测。该方法为蛋白质组学、免疫肽筛选等生物医学高通量检测提供了高效可靠的实验设计工具。

　　

在当今生物医学研究领域，高通量实验技术已成为不可或缺的研究手段。科学家们经常需要同时检测成百上千个样本，例如在免疫学研究中筛选能与特定T细胞受体结合的肽段表位，或在基因组学中大规模鉴定基因调控元件。传统的逐个检测方法成本高昂且效率低下，而组合池化（Combinatorial Pooling）策略通过将样本混合到少量反应池中，大幅提升了检测效率。然而，现有的池化设计方案往往难以兼顾多个关键需求：样本在池中的分布不均可能导致检测偏差，连续相关样本（如重叠的蛋白质序列）的识别存在困难，实验误差的检测能力不足。这些局限性严重制约了组合池化技术在精密生物测量中的应用效果。

针对这些挑战，北京航空航天大学与冷泉港实验室等机构的研究团队在《Bioinformatics》上发表了一项创新性研究，提出了"平衡恒重格雷码连续阳性检测"（Balanced Constant-Weight Gray Codes for Detecting Consecutive Positives，简称DCP-CWGC）新方法。该方法通过精心设计的编码策略，确保了样本在池中的均匀分布，实现了连续阳性样本的可靠检测，并具备强大的误差识别能力。

研究人员开发了两个核心算法：分支定界算法（Branch-and-Bound Algorithm，BBA）和递归组合分支定界算法（Recursive Combination with BBA，rcBBA）。BBA通过在地址-联合二分图中进行启发式深度优先搜索，构建接近完美平衡的DCP-CWGC；而rcBBA则通过递归组合短码来构建长码，显著提高了编码效率。这两种算法均集成在开源Python软件包codePUB中，可供研究人员直接使用。

平衡恒重格雷码的定义与特性

DCP-CWGC是一种特殊的二进制地址序列，需满足三个关键约束：相邻地址的OR和必须唯一，确保每对连续项有唯一标识；所有地址必须具有恒定汉明重量（Hamming weight），保证每个项接受相同数量的测试；相邻地址的汉明距离（Hamming distance）必须为2，这使得每对连续项的OR和重量保持恒定（r+1）。这些特性使得实验中出现错误时（如假阳性或假阴性），可以通过阳性池数量的异常变化进行检测。

平衡性分析

研究团队特别关注DCP-CWGC的平衡性，即每个池中包含的样本数量应尽可能均匀。平衡向量的偏差δ_C越小，池化安排越平衡，检测结果越稳定。当参数满足m≥2r+1时，最大长度的DCP-CWGC必然具有完美平衡性。

分支定界算法构建

BBA算法通过遍历地址-联合二分图来构建平衡DCP-CWGC。算法从任意初始地址开始，交替选择地址节点和联合节点，每次选择都优先考虑能最大程度维持平衡性的节点。该算法在合理时间内（如构建3000项编码仅需250秒）能生成接近完美平衡的编码方案。

递归组合方法

对于更长编码的构建，研究团队提出了递归组合策略。该方法通过将短DCP-CWGC的关联矩阵进行增强和组合，能构建接近理论最大长度的编码。理论证明，对于任意正整数r和m≥r+1，存在长度为min{(m选r),(m选r+1)+1}的DCP-CWGC。

计算复杂度与性能评估

实证分析表明，BBA的最优情况计算复杂度为Θ(n)，而最坏情况为O([r(m-r)]ⁿ)。rcBBA通过分解问题策略，显著降低了长码构建的计算复杂度。在运行时间方面，rcBBA在处理大规模编码构建时表现尤为出色，特别是在n接近理论最大值时优势明显。

平衡性评估

实验结果显示，两种算法生成的DCP-CWGC均具有优良的平衡特性。对于中等规模编码（n=150-950），偏差δ_C不超过8，接近完美平衡。BBA在小规模编码构建中平衡性更优，而rcBBA在处理大规模编码时能保持相当的平衡质量。

误差检测能力

在模拟实验中，研究人员测试了基于(18,6,n)DCP-CWGC的组合池化实验在不同错误率下的表现。由于DCP-CWGC的特性，阳性池数量预期恒为r+1=7，任何偏离此值的观测结果都表明存在实验误差。即使存在错误，候选项列表也能被有效缩小，如n=1000时，一个错误池仅产生约30个候选项，证明了该方法强大的误差检测能力。

该研究的创新之处在于首次将平衡性、恒重特性和连续阳性检测能力整合到统一的组合池化框架中。DCP-CWGC方案特别适用于生物序列分析场景，如免疫表位鉴定、CLE肽（CLAVATA3/ESR-related peptides）定位和基因组调控元件筛选等。在这些应用中，连续项往往代表重叠的氨基酸或核苷酸序列，DCP-CWGC能确保对这些相关序列进行无偏检测。

研究团队开发的codePUB软件包为生物医学研究人员提供了便捷的工具，支持灵活参数调整，满足不同实验场景的需求。该工作不仅推进了组合池化理论的发展，也为高通量生物检测实验提供了实用解决方案，有望在免疫学、植物生物学和基因组学等多个领域产生广泛影响。

未来研究方向可能包括扩展DCP-CWGC理论以处理更复杂的依赖关系模式，以及优化算法以适应超大规模编码构建需求。随着单细胞技术和空间组学等新兴领域的快速发展，对高效、可靠的高通量检测方法的需求将日益增长，而DCP-CWGC为代表的新型组合池化设计方法将在这一进程中发挥重要作用。