细菌中排序算法实现研究
Developing a Sorting Algorithm in Bacteria
DOI: 10.12677/hjcb.2025.154004, PDF,   
作者: 陈 梅*：中央民族大学信息工程学院，北京
关键词: 生物计算；细胞计算；DNA计算；排序；合成生物学；Bio-Computing； Cellular Computing； DNA Computing； Sorting； Synthetic Biology
摘要: 排序算法在信息科学中占据着不可替代的地位。细胞信息处理设备在生物治疗、生物修复等多个领域执行计算任务，然而活体内的排序算法研究仍属空白。本研究通过将经典算法设计策略与先进基因技术相结合，成功在大肠杆菌中设计并验证了一种遗传排序算法。该算法基于分治策略设计，利用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.
文章引用：陈梅. 细菌中排序算法实现研究[J]. 计算生物学, 2025, 15(4): 37-46. https://doi.org/10.12677/hjcb.2025.154004

参考文献

[1] Nissim, L., Wu, M., Pery, E., Binder-Nissim, A., Suzuki, H.I., Stupp, D., et al. (2017) Synthetic RNA-Based Immunomodulatory Gene Circuits for Cancer Immunotherapy. Cell, 171, 1138-1150.e15. [Google Scholar] [CrossRef] [PubMed]
[2] Gardner, T.S., Cantor, C.R. and Collins, J.J. (2000) Construction of a Genetic Toggle Switch in Escherichia coli. Nature, 403, 339-342. [Google Scholar] [CrossRef] [PubMed]
[3] Elowitz, M.B. and Leibler, S. (2000) A Synthetic Oscillatory Network of Transcriptional Regulators. Nature, 403, 335-338. [Google Scholar] [CrossRef] [PubMed]
[4] Moon, T.S., Lou, C.B., Tamsir, A., Stanton, B.C. and Voigt, C.A. (2012) Genetic Programs Constructed from Layered Logic Gates in Single Cells. Nature, 491, 249-253. [Google Scholar] [CrossRef] [PubMed]
[5] Bonnet, J., Yin, P., Ortiz, M.E., Subsoontorn, P. and Endy, D. (2013) Amplifying Genetic Logic Gates. Science, 340, 599-603. [Google Scholar] [CrossRef] [PubMed]
[6] Kim, H., Bojar, D. and Fussenegger, M. (2019) A Crispr/Cas9-Based Central Processing Unit to Program Complex Logic Computation in Human Cells. Proceedings of the National Academy of Sciences, 116, 7214-7219. [Google Scholar] [CrossRef] [PubMed]
[7] Xie, Z., Wroblewska, L., Prochazka, L., Weiss, R. and Benenson, Y. (2011) Multi-Input RNAi-Based Logic Circuit for Identification of Specific Cancer Cells. Science, 333, 1307-1311. [Google Scholar] [CrossRef] [PubMed]
[8] Green, A.A., Kim, J., Ma, D., Silver, P.A., Collins, J.J. and Yin, P. (2017) Complex Cellular Logic Computation Using Ribocomputing Devices. Nature, 548, 117-121. [Google Scholar] [CrossRef] [PubMed]
[9] Tamsir, A., Tabor, J.J. and Voigt, C.A. (2011) Robust Multicellular Computing Using Genetically Encoded NOR Gates and Chemical ‘Wires’. Nature, 469, 212-215. [Google Scholar] [CrossRef] [PubMed]
[10] Regot, S., Macia, J., Conde, N., Furukawa, K., Kjellén, J., Peeters, T., et al. (2011) Distributed Biological Computation with Multicellular Engineered Networks. Nature, 469, 207-211. [Google Scholar] [CrossRef] [PubMed]
[11] Gander, M.W., Vrana, J.D., Voje, W.E., Carothers, J.M. and Klavins, E. (2017) Digital Logic Circuits in Yeast with Crispr-Dcas9 NOR Gates. Nature Communications, 8, Article No. 15459. [Google Scholar] [CrossRef] [PubMed]
[12] Levskaya, A., Chevalier, A.A., Tabor, J.J., et al. (2005) Engineering Escherichia coli to See Light. Nature, 438, 441-442. [Google Scholar] [CrossRef] [PubMed]
[13] Friedland, A.E., Lu, T.K., Wang, X., Shi, D., Church, G. and Collins, J.J. (2009) Synthetic Gene Networks That Count. Science, 324, 1199-1202. [Google Scholar] [CrossRef] [PubMed]
[14] Callura, J.M., Cantor, C.R. and Collins, J.J. (2012) Genetic Switchboard for Synthetic Biology Applications. Proceedings of the National Academy of Sciences, 109, 5850-5855. [Google Scholar] [CrossRef] [PubMed]
[15] Shipman, S.L., Nivala, J., Macklis, J.D. and Church, G.M. (2016) Molecular Recordings by Directed CRISPR Spacer Acquisition. Science, 353, aaf1175. [Google Scholar] [CrossRef] [PubMed]
[16] Perli, S.D., Cui, C.H. and Lu, T.K. (2016) Continuous Genetic Recording with Self-Targeting Crispr-Cas in Human Cells. Science, 353, aag0511. [Google Scholar] [CrossRef] [PubMed]
[17] Farzadfard, F. and Lu, T.K. (2014) Genomically Encoded Analog Memory with Precise in Vivo DNA Writing in Living Cell Populations. Science, 346, Article 1256272. [Google Scholar] [CrossRef] [PubMed]
[18] Sheth, R.U., Yim, S.S., Wu, F.L. and Wang, H.H. (2017) Multiplex Recording of Cellular Events over Time on CRISPR Biological Tape. Science, 358, 1457-1461. [Google Scholar] [CrossRef] [PubMed]
[19] Shipman, S.L., Nivala, J., Macklis, J.D. and Church, G.M. (2017) Crispr-Cas Encoding of a Digital Movie into the Genomes of a Population of Living Bacteria. Nature, 547, 345-349. [Google Scholar] [CrossRef] [PubMed]
[20] Tang, W. and Liu, D.R. (2018) Rewritable Multi-Event Analog Recording in Bacterial and Mammalian Cells. Science, 360, eaap8992. [Google Scholar] [CrossRef] [PubMed]
[21] Chen, W.G., Han, M.Z., Zhou, J.T., et al. (2021) An Artificial Chromosome for Data Storage. National Science Review, 8, nwab028. [Google Scholar] [CrossRef] [PubMed]
[22] Ausländer, S., Ausländer, D., Müller, M., Wieland, M. and Fussenegger, M. (2012) Programmable Single-Cell Mammalian Biocomputers. Nature, 487, 123-127. [Google Scholar] [CrossRef] [PubMed]
[23] Choi, S., Lee, G. and Kim, J. (2022) Cellular Computational Logic Using Toehold Switches. International Journal of Molecular Sciences, 23, Article 4265. [Google Scholar] [CrossRef] [PubMed]
[24] Shao, J., Qiu, X., Zhang, L., Li, S., Xue, S., Si, Y., et al. (2024) Multi-Layered Computational Gene Networks by Engineered Tristate Logics. Cell, 187, 5064-5080.e14. [Google Scholar] [CrossRef] [PubMed]
[25] Jinek, M., Chylinski, K., Fonfara, I., Hauer, M., Doudna, J.A. and Charpentier, E. (2012) A Programmable Dual-RNA-Guided DNA Endonuclease in Adaptive Bacterial Immunity. Science, 337, 816-821. [Google Scholar] [CrossRef] [PubMed]
[26] Goodwin, S., McPherson, J.D. and McCombie, W.R. (2016) Coming of Age: Ten Years of Next-Generation Sequencing Technologies. Nature Reviews Genetics, 17, 333-351. [Google Scholar] [CrossRef] [PubMed]
[27] Xu, J. (2016) Probe Machine. IEEE Transactions on Neural Networks and Learning Systems, 27, 1405-1416. [Google Scholar] [CrossRef] [PubMed]

为你推荐