计算含重叠区域的大型基因组区间总长度的高效Python实现方案

核心思路 #

解决这个问题最高效的方式是先排序，再合并重叠/相邻区间，最后计算合并后区间的总长度。排序保证我们可以线性遍历处理所有区间，合并过程仅需一次遍历，整体时间复杂度为O(n log n)（主要来自排序步骤），完全适配大规模数据集。

实现步骤 #

1. 排序区间：按每个区间的起始坐标从小到大排序，确保后续能按顺序处理重叠情况。
2. 合并重叠区间：初始化一个合并列表，遍历每个区间：
   • 如果当前区间与合并列表的最后一个区间重叠（当前区间起始 ≤ 最后一个区间的终止），则合并两个区间（更新最后一个区间的终止坐标为两者的最大值）。
   • 如果不重叠，直接将当前区间加入合并列表。
3. 计算总长度：遍历合并后的所有区间，累加每个区间的（终止坐标 - 起始坐标）。

Python代码实现 #

def calculate_unique_interval_length(intervals):
    if not intervals:
        return 0
    
    # 按区间起始坐标排序
    sorted_intervals = sorted(intervals, key=lambda x: x[0])
    merged = [sorted_intervals[0]]
    
    for curr_start, curr_end in sorted_intervals[1:]:
        last_start, last_end = merged[-1]
        if curr_start <= last_end:
            # 重叠或相邻，合并区间
            merged[-1] = (last_start, max(last_end, curr_end))
        else:
            merged.append((curr_start, curr_end))
    
    # 计算去重后的总长度
    return sum(end - start for start, end in merged)

测试示例 #

针对你给出的排序后区间列表：

test_intervals = [(3, 9), (3, 5), (6, 9)]
print(calculate_unique_interval_length(test_intervals))  # 输出：6

结果符合预期，合并后的区间为[(3,9)]，长度为9-3=6。

边界情况处理 #

• 空区间列表：返回0
• 单个区间：直接返回区间长度
• 相邻区间（如[(1,3), (3,5)]）：合并为[(1,5)]，总长度4
• 完全包含的区间（如[(2,10), (3,5)]）：合并后仍为[(2,10)]，长度8

内容的提问来源于stack exchange，提问作者zhang