排序查找与哈希在生信中的应用

更新：2026-10-13；状态：可用；验证范围：Python官方资料核对；二分边界与重叠k-mer人工例子已运行。

用查找坐标和统计短序列理解排序、二分与哈希的条件和成本。

为什么先排序

将坐标或ID排序后，可以快速定位范围。Python比较排序具有稳定性，但染色体字符串的字典序不一定等于生物学常用顺序；排序键和坐标版本必须明确。

二分查找要求输入按同一规则有序，并能高效随机访问。每次比较排除一半范围，数组上的比较次数为O(log n)。查找后插入数组仍可能需要O(n)移动，不能把“二分定位”误说成整个插入都为O(log n)。

一个可核对的例子

已排序表 [1,3,3,8] 中，3的左边界为索引1，采用0起始索引。lower_bound返回首个不小于目标的位置；目标不存在时也返回插入位置，必须额外检查才能宣称找到了值。

哈希与k-mer计数

哈希表把键映射到存储位置，通常支持期望O(1)查找，但碰撞和键计算成本仍存在。对序列 ATATAT统计长度2的重叠片段，可得AT=3、TA=2，总数5。不可跨读段连接后统计，也需定义大小写、模糊碱基和反向互补是否归并。

教学代码采用Python切片和Counter；每个长度k的片段构造和哈希都有成本，不能在k也增长时一概称整个过程O(L)。生产计数器可能采用编码、滚动哈希和磁盘分块。

运行与边界

基础算法程序已运行上述查找和计数。它不是完整变异区间检索或大规模k-mer软件；区间重叠还要考虑起止坐标及半开/闭区间规则，见基因组坐标与区间。

依据：Python bisect、Counter、排序指南。