细菌中排序算法实现研究

Developing a Sorting Algorithm in Bacteria

摘要: 排序算法在信息科学中占据着不可替代的地位。细胞信息处理设备在生物治疗、生物修复等多个领域执行计算任务，然而活体内的排序算法研究仍属空白。本研究通过将经典算法设计策略与先进基因技术相结合，成功在大肠杆菌中设计并验证了一种遗传排序算法。该算法基于分治策略设计，利用CRISPR/Cas9系统通过递归方式将信号划分为较大组与较小组实现排序，结果经由第二代测序技术进行分析。湿实验验证了该排序算法的有效性。此外，算法中提供的分组方法亦代表了一种高效的分类机制。本研究通过排序与分类的基因电路实现来推动智能复杂细胞信息处理设备的构建。

Abstract: The sorting algorithm occupies an irreplaceable position in information science. Cellular information-processing devices execute computing tasks in various fields, such as biotherapy and bioremediation. However, the sorting algorithm in vivo is still lacking. Through combining classical algorithm-design strategy with advanced genetic technologies, this study has successfully designed and tested a genetic sorting algorithm in the bacterium Escherichia coli. This sorting algorithm is designed based on the divide-and-conquer algorithm-design strategy. It enables sorting through a recursive grouping of the signals into the greater group and the lesser group with clustered regularly interspaced short palindromic repeats/CRISPR-associated9 system. The result is analyzed by next-generation sequencing. Wet-lab experiments verified the validity of this sorting algorithm. In addition, the grouping method provided in this sorting algorithm also represents an efficient classification method. This study will advance the construction of intelligent and complex cellular information-processing devices through sorting and classification.

1. 引言

生物技术的发展使研究人员能够合理操控遗传信息流，构建细胞信息处理设备。这类设备因其可与自然界交互执行计算任务(如生物治疗、生物修复等领域)，具有广泛的应用前景。例如，当检测到两种特定肿瘤标志物时，用于肿瘤治疗的细胞“与门”会生成组合免疫调节输出以激活治疗响应[1]。受电子计算机强大信息处理能力的启发，科研人员已构建出众多细胞信息处理设备。这些设备主要聚焦于模拟电子计算功能，包括触发开关[2]、振荡器[3]、逻辑门[4]-[11]、传感器[12]、计数器[13]、交换器[14]、存储器[15]-[21]及逻辑单元[22]-[24]。这些设备将计算科学的信息处理思想与体内信息处理方法相结合，展现出细胞计算设备的巨大潜力。

排序算法作为信息处理中的核心操作之一，在数据组织、模式识别与决策优化中发挥着不可替代的作用。它能够将杂乱无章的数据按升序或降序排列，从而为后续分析提供结构化基础。在细胞信息处理设备中，因为细胞内资源有限，排序算法能够甄别信号优先级，引导细胞将有限的资源投入到最关键的生理响应中，从而实现决策智能化与资源利用最优化。然而在活体内开发排序算法面临诸多挑战：需要对多个信号进行大量比较运算并记录结果。由于细胞体积微小且资源有限，必须通过精巧设计和高效工具来降低实现复杂度。

本研究开发了一种细菌排序算法(SAB)。该算法基于分治策略设计，通过CRISPR/Cas9系统与第二代测序技术实现，并经由湿实验验证了其有效性。

2. 结果

2.1. 整体设计

为实现信号排序，本研究为每个信号设定特定短DNA序列作为特征序列。细菌排序算法通过操控这些特征序列来实现信号处理。该算法基于分治策略进行设计。分治策略是最经典的算法设计策略之一，其核心思想是将原问题递归分解为两个或多个相互独立的子问题，直至子问题简化为可直接求解的形式，最后将子问题的解合并形成原问题的解。本算法首先将所有待处理信号划分为较大组和较小组；随后对每个分组继续执行相同的二分操作，直至组内仅剩单个信号。最终通过整合所有分组结果即可呈现信号的排序(图1和图S1)。

2.2. 分组系统设计

CRISPR/Cas9系统在本细菌排序算法中作为分组工具使用。作为一项革命性的基因组编辑技术，CRISPR/Cas9系统已获得广泛应用。该系统通过20 bp的sgRNA引导Cas9核酸酶靶向具有PAM序列(5'-NGG-3')的DNA位点，由Cas9在靶标位点催化产生DNA双链断裂[25]。质粒发生双链断裂通常会导致其自身丢失，因此通过诱导质粒产生双链断裂成为清除质粒的有效手段。本算法利用CRISPR/Cas9系统通过诱导双链断裂清除质粒来实现分组功能。研究设计了三质粒系统以递归方式完成信号分组(图2)。该分组过程通过清除含有较小组信号特征序列的质粒来实现分组，最终通过特征序列是否被清除来判定信号所属组别。

本研究采用第二代测序技术对细菌排序算法的结果进行分析。该技术是一种大规模并行测序方法，可同时对数百万乃至数十亿条DNA链进行测序[26]。考虑到pL质粒可能无法被完全清除，现定义K值用于结果分析如下：

$K\left(\frac{A}{B}\right)=\frac{信�A特征序列�}{信�B特征序列�}$

通过二代测序技术对特征序列进行定量分析，并依据K值的变化情况判定最终排序结果(图3和图S2)。

Figure 1. Schematic representation of the sorting principle. Multiple independent types of cells need to be constructed to enable sorting. In these cells, some group all signals, while some group signals in a certain group are divided by another cell. The cells are used in a pre-determined order to perform sorting

图1. 排序原理示意图。为实现排序功能，需要构建多种独立类型的细胞。这些细胞中，部分负责对所有信号进行分组，另一部分则对经其他细胞划分的特定信号组进行再分组。所有细胞按预定顺序执行排序操作

Figure 2. Schematic representation of the three-plasmid system. The three-plasmid system is composed of plasmid pG, pL, and pCOM. Plasmid pG contains the characteristic sequences of the signals in the greater group. Plasmid pL contains the characteristic sequences of the signals in the lesser group. Plasmid pCOM produces sgRNA: Cas9 complex, for causing a double-stranded break (DSB) in the pL under the control of a signal that needs to be grouped

图2. 三质粒系统示意图。该体系由pG、pL和pCOM三种质粒构成：pG质粒携带较大组信号的特征序列；pL质粒携带较小组信号的特征序列；pCOM质粒在待分组信号调控下表达sgRNA:Cas9复合体，用于在pL质粒上引发DNA双链断裂

Figure 3. Schematic representation of the result analysis. To analyse the result, a fragment of base sequence is designed and the characteristic sequences are inserted into the base sequence. Before and after grouping, polymerase chain reaction (PCR) is performed to obtain the characteristic sequences. The PCR products are sequenced and counted using NGS. K value is computed according to the counting result. The change in K value indicates the grouping result. In the grouping process, the number of plasmids containing the characteristic sequence of the lesser signal dramatically decreases, even if not totally cleared. Therefore, the K value changes dramatically. The clearance of the characteristic sequence is determined according to this change

图3. 结果分析示意图。为进行结果分析，首先设计基础碱基序列片段并将特征序列插入其中。在分组操作前后，通过聚合酶链式反应(PCR)获取特征序列，对PCR产物进行二代测序(NGS)和定量分析，根据计数结果计算K值。K值的变化用于判定分组结果：在分组过程中，即使未被完全清除，携带较弱信号特征序列的质粒数量也会急剧减少，这种显著的数量变化导致K值发生剧烈波动，最终根据该波动判定特征序列的清除情况

2.3. 湿实验

本研究利用细菌排序算法，在大肠杆菌中对阿拉伯糖(Arab)、异丙基-β-D-硫代半乳糖苷(IPTG)、无水四环素(aTc)及鼠李糖(Rham)四种信号分子进行了排序。假设四种信号的强度关系为Arab > Rham > IPTG > aTc，图4展示了对应的基因电路设计及排序结果。

Figure 4. Sorting four signals using bacteria. (a) Cell1 divided the four signals into the greater group and the lesser group. The K value of arabinose and rhamnose remained the same before and after the grouping process, indicating that the two signals are in one group and the other two signals are in the other group. The K value of IPTG and rhamnose significantly decreased, indicating that the IPTG is cleared. The K value of aTc and rhamnose also significantly decreased, indicating that the aTc is cleared. Consequently, the results demonstrated that the greater group contained arabinose and rhamnose, and the lesser group contained IPTG and aTc. (b) Cell2 grouped the signals in the greater group. The K value of arabinose and rhamnose significantly increased, indicating that rhamnose is cleared. Consequently, arabinose is greater than rhamnose. (c) Cell3 grouped the signals in the lesser group. The K value of aTc and IPTG significantly decreased, indicating that the aTc is cleared. Consequently, IPTG is greater than aTc. Combining the results of cell1 and cell2 with cell3, the order is Arab > Rham > IPTG > aTc. Values and error bars represent the mean ± SD of three replicates

图4. 利用细菌对四种信号进行排序。(a) Cell1将四种信号划分为较大组和较小组。阿拉伯糖和鼠李糖的K值在分组前后保持稳定，表明这两种信号属于同一分组，而另外两种信号属于另一分组。IPTG和鼠李糖的K值显著下降，表明IPTG被清除；aTc和鼠李糖的K值也显著下降，表明aTc被清除。由此证明较大组包含阿拉伯糖和鼠李糖，较小组包含IPTG和aTc。(b) Cell2对较大组信号进行再分组。阿拉伯糖与鼠李糖的K值显著上升，表明鼠李糖被清除，因此阿拉伯糖强度大于鼠李糖。(c) Cell3对较小组信号进行再分组。aTc与IPTG的K值显著下降，表明aTc被清除，因此IPTG强度大于aTc。综合cell1、cell2与cell3的实验结果，最终排序为：阿拉伯糖 > 鼠李糖 > IPTG > aTc。图中数据及误差线表示三次重复实验的平均值 ± 标准差

为实现排序功能，本研究设计了三种工程细胞。每种细胞均包含一个三质粒系统。为确保三质粒系统的稳定存在并便于菌株构建，每种质粒均采用不同的复制起点(图4中p15A、CloDF13和pMB1)和不同抗性标记(图4中cmR、smR和Kan)。同类质粒在不同种类细胞中(如cell1与cell3中的pG质粒)可具有不同的复制起点和抗性标记。在cell1和cell3中，CRISPR/Cas9系统的靶序列为5′-gacctgccctgtgcagctgtggg-3′，而cell2中则为5′-aactgcaatttattcatatcagg-3′。Cell1和cell3采用IPTG诱导型表达系统执行分组操作，cell2则使用阿拉伯糖诱导型表达系统。表1列出了特征序列及其碱基序列，表2展示了测序计数结果。

Table 1. The characteristic sequences and base sequences (5′-3′)

表1. 特征序列和基础序列(5′-3′)

特征序列	arabinose	aactgcaatttattcacgat
	rhamnose	aactgcaatttattcatatc
	IPTG	gacctgccctgtgcagcacc
	aTc	gacctgccctgtgcagctgt
基础序列(PCR和NGS中使用的引物用斜体指示，“x”指示插入的特征序列)	Cell1	aagtttatctgtacaacaggcaagctgcccgttccctggcctaccttggtcaccacactcacttatggagtgcaatgcttcgctcgttatcccgaccxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxacatgaagcagcacgattttttcaagtccgcgatgcccgagggctacgttcaagaacgcactataagttttaaggacgacgggacatataagacccgtgccgaggtgaagtttgaaggcgatactttggtgaacagaattgagctgaaggggatcgactttaaagaagacggaaatatcctgggacacaagctggagtataacttcaatagccataacgtttacattacagctgacaaacagaaaaatggtataaaagccaacttcaagatccggcataatgttgaagatggcagcgtgcagctggctgat
	Cell2	ttcggcctattggttaaaaaatgagctgatttaacaaaaatttaacgcgaattttaacaaaatattaacgtttacaatttcaggtggcacttttcggggaaatgtgcgcggaacccctatttgtttatttttctaaatacattcaaatatgtatccgctcatgaattaattcttagaaaaactcatcgagcatcaaatgaxxxxxxxxxxxxxxxxxxxxxxxattatcaataccatatttttgaaaaagccgtttctgtaatgaaggagaaaactcaccgaggcagttccataggatggcaagatcctggtatcggtctgcgattccgactcgtccaacatcaatacaacctattaatttcccctcgtcaaaaataaggttatcaagtgagaaatcaccatgagtgacgactgaatccggtg
	Cell3	aagtttatctgtacaacaggcaagctgcccgttccctggcctaccttggtcaccacactcacttatggagtgcaatgcttcgctcgttatcccgaccxxxxxxxxxxxxxxxxxxxxxxxacatgaagcagcacgattttttcaagtccgcgatgcccgagggctacgttcaagaacgcactataagttttaaggacgacgggacatataagacccgtgccgaggtgaagtttgaaggcgatactttggtgaacagaattgagctgaaggggatcgactttaaagaagacggaaatatcctgggacacaagctggagtataacttcaatagccataacgtttacattacagctgacaaacagaaaaatggtataaaagccaacttcaagatccggcataatgttgaagatggcagcgtgcagctggctgat

Table 2. The counting results

表2. 计数结果

	Cell	Characteristic sequence	Replicate 1	Replicate 2	Replicate 3
Before grouping	Cell1	Rham	46022	45801	46641
		Arab	45870	45601	46449
		aTc	10661	10658	10212
		IPTG	10735	10708	10256
	Cell2	Rham	770707	219871	420490
		Arab	1998927	562992	1025309
	Cell3	aTc	4124	3641	3668
		IPTG	3322351	3061058	2811369
After grouping	Cell1	Rham	3176	2995	2806
		Arab	3427	3223	2991
		aTc	3	0	5
		IPTG	5	0	7
	Cell2	Rham	5818	4606	4890
		Arab	1634990	1165340	1318921
	Cell3	aTc	85	86	119
		IPTG	3290052	2718175	3435341

3. 结论和讨论

本研究开发了一种可扩展的细菌排序算法。首先，该算法架构具有可扩展性：细菌排序算法中每种细胞类型均可独立执行分组操作，便于灵活添加细胞单元。与传统的体内分布式计算系统相比，基于分治策略的算法架构避免了使用化学导线(依赖特定分子在细胞间传递信息)，有效降低了设计难度。其次，分组细胞单元具备可扩展性：通过构建三质粒系统在每个细胞内递归执行分组，降低了实现复杂度。该基于CRISPR/Cas9系统的三质粒设计不受信号数量影响，质粒数量不随信号规模增加而改变，仅需扩展特征序列即可处理更多信号。根据质粒容量估算，该算法具备处理数十种信号的潜力。

该细菌排序算法通过提供灵活分类方法，将推动智能细胞信息处理设备的构建。分类是众多智能任务的基础，本算法提供的分组机制代表了一种高效分类方法。三质粒系统中pG与pL质粒承载的信号数量无需对等，支持对称与非对称分组模式(图S3)，使细胞能按类别处理信号：可优先处理重要信号(较大组)，或忽略次要信号(较小组)。同时，细胞可参照同组其他信号特征进行决策，基于群体特征预测作出判断。

通过引入算法设计策略，该研究还将促进复杂细胞信息处理设备的开发。细胞的信息处理模式与电子设备存在本质差异[27]：例如细胞不像电子设备那样通过级联布尔逻辑门执行复杂功能。简单模仿电子设备的工作方式并非编程细胞的最佳途径，因此探索新的构建策略至关重要。算法在发挥电子计算机信息处理能力应用于各领域时具有不可替代的作用——电子计算机硬件仅执行特定逻辑运算，而算法根据任务特性和计算硬件特点，提供完成任务的方法步骤。正是算法指导计算机实现人脸识别、商品推荐、三维渲染等多样化任务。我们期待本研究能推动基于细胞本质特性的算法开发，为实现更复杂功能奠定基础。

尽管该细菌排序算法具备很多优势，但其实际应用仍面临细胞内代谢负荷、遗传稳定性及计算效率等现实挑战。递归性三质粒系统和CRISPR/Cas9元件的持续表达可能引发生长迟滞，限制其处理效率；依赖荧光报告等生物读出方法，存在速度慢、通量低和成本高的问题。为突破这些瓶颈，未来改进可聚焦于：通过基因组整合或研发新型Cas蛋白等工具来增强系统稳定性；结合微流控或新型测序技术开发高通量、快速的电/光信号读出方法，从而向更高效、智能的生物信息处理系统演进。

4. 方法

完成设计后，质粒由重庆英茂盛业生物科技有限公司合成。选择大肠杆菌BL21(DE3)菌株(F⁻ ompT hsdSB (rB-mB-) gal dcm (DE3))作为cell1和cell3的宿主，大肠杆菌MG1655菌株(F⁻ λ⁻ ilvG⁻ rfb-50 rph-1)作为cell2的宿主。对于每种细胞，首先共转化pG与pL质粒，随后转化pCOM质粒，采用标准热激转化法。所有细胞均在LB培养基中培养。

排序实验流程如下：初始阶段将细胞接种于含25 µg/mL氯霉素、50 µg/mL卡那霉素和50 µg/mL链霉素的LB培养基，37℃振荡培养过夜后，按5 µL菌液转入5 mL新鲜培养基的比例进行稀释，新培养基在保留氯霉素的同时添加特定信号分子。细胞继续在37℃培养12-16小时。各信号分子终浓度为：无水四环素100 ng/mL、阿拉伯糖0.2%、IPTG 0.1 mM、鼠李糖0.1 mg/mL。

针对每种细胞，通过PCR扩增碱基序列，扩增产物采用二代测序技术进行测序。根据测序结果统计各信号特征序列的数量。Cell1和cell2的测序及计数工作由北京君唯诺生物技术有限公司完成，cell3由北京阅微基因科技有限公司完成。

附录：补充材料

Figure S1. The pseudo-code description of SAB

图S1. SAB伪代码

Figure S2. The pseudo-code description of grouping process

图S2. 分组过程伪代码

Figure S3. Schematic representation of classification in asymmetric ways (random sequence is used to ensure that the base sequences in pL and pG are of the equal length). (a) Finding the maximum. (b) Finding the minimum. (c) Dividing five signals into two groups

图S3. 非对称分类示意图（使用随机序列确保pL和pG中的碱基序列长度相等）。(a) 寻找最大值。(b) 寻找最小值。(c) 将五个信号分成两组

NOTES

^*通讯作者。