实用开发模块

kilb

klib是一个轻量级的 C 语言库,包含常用的数据结构和算法。大多数组件不依赖外部库,并且彼此独立。要使用该库的组件,只需将几个文件复制到您的源代码树中,无需担心库依赖性。Klib 在生物信息学中被广泛应用,例如 minimap2 使用了部分库作为其基础数据结构。

Klib 追求高效和小内存占用。在速度和内存使用方面,一些组件(如哈希表、B 树、向量和排序算法)是所有编程语言中类似算法或数据结构中最有效的实现之一。

与 C 的标准库(std)相比,Klib 运行速度更快,占用内存更少。但是,由于 Klib 主要由 C 语言的宏实现,调试难度较大,并且需要手动管理内存,因此请根据实际情况使用。

用法:

klib文件夹存放修改后的klib代码,docs文件夹存放常用头文件的教程,如kvec.h, kseq.h, kthread.h等。

基于四俄国人思想的双序列比对算法模块

简介:

基于四俄国人思想的双序列比对算法是一种并行求解双序列比对的算法,对分治法-线性空间改进算法进行进一步的并行化,减少了计算量。

该库不仅可以直接通过程序调用,也可以通过库进行调用。

建议在序列相似度较低时使用。

用法:

参考 usage

项目地址:

项目路径

文献引用:

Wei, Y., Zhou, T., Zhai, Y., Yu, L., & Zou, Q. (2025). FORAlign: accelerating gap-affine DNA pairwise sequence alignment using FOR-blocks based on Four Russians approach with linear space complexity. Briefings in Bioinformatics, 26(1), bbaf061.

并行后缀数组

简介:

部分后缀数组方法(如 DC3 等)采用基数排序完成,由于基数排序并行较为容易,因此有一些开发并行基数排序以实现并行后缀数组的方法。本项目进行了部分整理。

注意:由于 Cilk 已经被 gcc-7 弃用,因此采用 OpenMP 进行并行,代码中对于 OpenMP 的支持不足。

用法:

参考 usage

项目地址

项目路径

FM-index

简介:

FM-index 是一种基于 Burrows-Wheeler 变换(BWT)的压缩全文索引结构,广泛应用于生物信息学中的序列比对任务。它兼具压缩性与高效查询性能,能够在不解压原始数据的情况下完成快速的子串搜索。本模块实现了一个基础的 FM-index,旨在为开发人员在构建比对算法或处理大规模基因序列数据时提供参考与帮助。该实现具有较强的可读性和扩展性,适合用于学习、研究或作为更复杂系统的构建基础。

特点:

1. 给出divsufsort, Big-BWTCaPS-SA三种后缀数组构造方式,适用于不同大小的数据集

2. 使用sdsl的基于哈夫曼编码的小波树存储BWT,支持快速的rank和select操作

3. 给出三种模式的模式匹配函数,支持不同灵敏度的搜索

项目地址

仍在开发测试中