4.1 邻接算法实现 15

4.2 快速邻接算法的基本思想及实现 17

5 采用 neo4j 存储微生物系统树及算法优化测试 21

5.1 neo4j 云环境搭建 21

5.2 利用 neo4j 存储系统树拓扑结构 24

5.3 使用 neo4j 进行查询 26

5.4 算法优化前后运行时间的比较 27

6 结论与展望 29

6.1 结论 29

6.2 后续研究及应用展望 29

致谢 30

参考文献 31

1 绪论

1.1 课题研究背景

近年来分子生物学的研究发展迅猛，生物信息数据的规模也不断的增加，并且形 成了数量巨大的生物信息库。上世纪第二十年代中期以来，基因测序技术分析的不断 发展完善，物种逐渐发展到分子水平的进化，建立起了一套理论和方法依赖于核酸和 蛋白质序列信息[1]。破解不同生物基因组 DNA 序列信息以及其中所蕴含的相关遗传 学背景已经成为生物学和医学研究的主要学科领域。将重要的人类病原菌、植物病原 菌和腐生菌等微生物进行基因组序列的测定以及相互遗传进化的关系的研究，不仅可 以推动关于致病机制、微生物和宿主相互作用等的基础研究，而且能帮助生物研究者 快速准确地筛选出耐药微生物群从而更好地寻找抗菌药物靶点，另一方面它能够推动 疫苗以及抗菌药物的研制和开发。在大数据时代的今天，生物信息学的研究必定会有 明显的推进。

与此同时，一种全新的数据库理念——NoSQL(Not only SQL)正得到广泛的推广。 NoSQL 泛指非关系型数据库，它摆脱了原有(Key,Value)的存储模型，这更加适用于 现在超大规模和高并发性的 web 数据[2]。这其中的典型代表就是图形数据库，它将整 个数据集通过大型稠密的网络结构进行存储。neo4j 则是全球范围内领先并得到广泛 使用的图形数据库，它基于 java 实现，在很好用，轻便灵活，嵌入式功能强大，用 JAVA，Python，PHP, .NET 等语言实现，并可以支持数十亿的节点数[3]。在该数据 库中，数据结构并不必要，它将传统的数据存储转化为点和边的形式，这在很大程度 上简化了原有的记录与查询模式，提高了使用效率。论文网

本课题将图数据库和微生物基因研究结合起来，利用 neo4j 图数据库在云环境下 处理微生物基因组的遗传进化信息，更直观地观察和分析物种间进化特征，分析遗传 距离，了解生物信息。

1.2 研究意义

生物的基因测序及其蕴含的相关的遗传进化内容之所以是长盛不衰的研究方向， 是因为通过上述的生物遗传信息的获取，不仅可以掌握各个物种的遗传特点和生物特 性，而且可以将不同生物通过一定的算法组成遗传进化的网络，以此了解物种间的简 化关系，并推断生物上亿万年来的进化轨迹。在生物圈中，在地球上存在了 37 亿年文献综述