将重叠的数字范围合并为连续范围

Question

我正在尝试将一系列基因组坐标合并为连续范围，并提供一个用于跨间隙合并的附加选项。

例如，如果我有基因组范围，[[0, 1000], [5, 1100]]我希望结果是[0, 1100]. 如果偏移选项设置为100，并且输入为 ，[[0, 1000], [1090, 1000]]我将再次希望结果为[0, 1100]。

我已经实现了一种执行此操作的方法，该方法按顺序逐步完成对齐，并尝试合并上一个结束位置和下一个起始位置，但它失败了，因为实际结果的长度不同。例如，我[[138, 821],[177, 1158], [224, 905], [401, 1169]]的列表中的结果按开始位置排序。答案应该是[138, 1169]，但我却得到了[[138, 1158], [177, 905], [224, 1169]]。显然，我需要考虑的不仅仅是前一个结束和下一个开始，但我还没有找到一个好的解决方案（最好不是一大堆 if 语句）。有人有什么建议吗？

def overlap_alignments(align, gene, overlap):
    #make sure alignments are sorted first by chromosome then by start pos on chrom
    align = sorted(align, key = lambda x: (x[0], x[1]))
    merged = list()
    for i in xrange(1, len(align)):
        prv, nxt = align[i-1], align[i]
        if prv[0] == nxt[0] and prv[2] + overlap >= nxt[1]:
            start, end = prv[1], nxt[2]
            chrom = prv[0]
            merged.append([chrom, start, end, gene])
    return merged

Answer 1

Python 附带电池：

from itertools import chain

flatten = chain.from_iterable

LEFT, RIGHT = 1, -1

def join_ranges(data, offset=0):
    data = sorted(flatten(((start, LEFT), (stop + offset, RIGHT))
            for start, stop in data))
    c = 0
    for value, label in data:
        if c == 0:
            x = value
        c += label
        if c == 0:
            yield x, value - offset

if __name__ == '__main__':
    print list(join_ranges([[138, 821], [900, 910], [905, 915]]))
    print list(join_ranges([[138, 821], [900, 910], [905, 915]], 80))

结果：

[(138, 821), (900, 915)]
[(138, 915)]

它是如何工作的：我们这样标记每个起点和终点，然后进行排序，然后我们简单地对每个起点进行向上计数，对每个终点进行向下计数。如果我们访问了相同数量的起点和终点，则我们有一个闭合（连接）范围。